自己动手写算法之快速排序

交换排序法->快速排序
快速排序使用分治法策略来把一个序列分为两个子序列

算法步骤：

1. 从数列中挑出一个元素，称为 "基准"（pivot）

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 （相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

* 比较复杂度：O(n㏒n)
* 交换(赋值)复杂度：O(n㏒n)
* 优点：比一般的排序都要快

public static void quickSort(Integer[] array) {
	if (array == null || array.length== 0) {
	     return;
	}
	quickSort(array,0,array.length-1);		
}

 

   private static void quickSort(Integer[] array, final int start, final int end){
		//数组长度<=1退出
		if(start>=end){
			return;
		}
		//数组长度==2,比较两个元素的大小
		if(end-start==1){
			if(array[start]>array[end]){
				swap(array,start,end);
			}
			return;
		}
		
		//用来进行比较的数
		int compareNumber = array[start];
		int middlePosition = 0;
		int i = start;
		int j = end;
		for(;;i++,j--){
			
			//从数组首端开始迭代(不包括compareNumber)，如果数组的数<compareNumber，不做移动
			while(array[i]<compareNumber&&i<j){
				i++;
			}		
			//从数组尾端迭代，如果数组的数>=compareNumber，不做移动
			
			while(array[j]>compareNumber&&i<j){
				j--;
			}			
			
			if(i>=j){
				if(array[j]>compareNumber){
					middlePosition = j;
				}else{
					middlePosition = (j+1);
				}
				break;
			}
			//从数组首端开始迭代，得到大于compareNumber的数array[i]，此时从尾端迭代直至得到<=compareNumber的数
			//array[j],交换这两个数的位置，然后继续迭代
			swap(array,i,j);
		}
		//递归排序
		quickSort(array,start,middlePosition-1);
		quickSort(array,middlePosition,end);
	}

 

public static void swap(Object[] array,int a,int b){
		Object temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}