本文共 2262 字，大约阅读时间需要 7 分钟。

快要秋招了，可能会手撕快排，提前准备，记录一下。

方式1: partition版本

package scu.stone.spring;import java.util.Arrays;public class QuickSort {
   	/**	 * 快排，是冒泡的一个改进；注意：快排【不稳定】，它有可能打破原来值为相同的元素之间的顺序。	 * 采用分治法，通过一趟排序将数据分为两部分，比基准值小的元素放在基准值的前面，比基准值大的元素放在基准后面；	 * 递归子序列	 * 最好情况和平均时间复杂度都是O(nlogn) ；最坏时间复杂度为O(n^2),空间复杂度为O(1)	 */	public static void main(String[] args) {
   		int [] array = {
   1,2,9,7,6,5,8,4,3};		int [] array2 = {
   1,2,9,7,6,5,8,4,3};		quickSort(array, 0, array.length-1);		System.out.println(Arrays.toString(array));		System.out.println("======================");		quickSort_partition(array2, 0, array.length-1);		System.out.println(Arrays.toString(array2));	}	public static void quickSort_partition(int [] array,int start, int end) {
   		if (start >= end) {
   			return;		}		int index = patition(array, start, end);		quickSort_partition(array, start, index-1);		quickSort_partition(array, index+1, end);	}		public static int patition(int[] array,int start,int end) {
   		int flag = array[start]; //哨兵		while (start < end)		{
   			while(start < end && array[end] >= flag )  //从后往前 				end--;			swap(array,start, end);  //遇到比哨兵小的，就交换			while (start < end && array[start] <= flag)   //从前往后				start++;			swap(array, start, end); //遇到比哨兵大的，就交换		}		return start;	}		public static void swap(int[] array,int i,int j) {
   		int temp = array[i];		array[i] = array[j];		array[j] = temp;	}}

方式二： 填坑版本

public static void quickSort(int[] array,int low,int high) {
   		if (array == null || array.length <= 0) {
   			return;		}		if (low >= high) {
   			return;		}		int left = low;		int right = high;		int key = array[left];  //挖坑1:保存基准值		while (left < right) {
   			while (left < right && array[right] >= key) {
   				right--;			}			array[left] = array[right]; //挖坑2:从后向前找到比基准值小的元素，插入到基准位置坑1中			while(left < right && array[left] <= key) {
   				left++;			}			array[right] = array[left]; //挖坑3:从前往后找到比基准大的元素，放到刚才挖的坑2中		}//end while		array[left] = key;  //基准值填补到坑3中，准备分治递归快排				System.out.println("Sorting: " + Arrays.toString(array));		quickSort(array, low, left-1);  //递归		quickSort(array, left+1, high);	}

转载地址：http://nvdgi.baihongyu.com/