学步园

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

算法步骤： 

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

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

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

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

Java代码  

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

Java代码  

1. private static void quickSort(Integer[] array, final int start, final int end){  
2.         //数组长度<=1退出  
3.         if(start>=end){  
4.             return;  
5.         }  
6.         //数组长度==2,比较两个元素的大小  
7.         if(end-start==1){  
8.             if(array[start]>array[end]){  
9.                 swap(array,start,end);  
10.             }  
11.             return;  
12.         }  
13.           
14.         //用来进行比较的数  
15.         int compareNumber = array[start];  
16.         int middlePosition = 0;  
17.         int i = start;  
18.         int j = end;  
19.         for(;;i++,j--){  
20.               
21.             //从数组首端开始迭代(不包括compareNumber)，如果数组的数<compareNumber，不做移动  
22.             while(array[i]<compareNumber&&i<j){  
23.                 i++;  
24.             }         
25.             //从数组尾端迭代，如果数组的数>=compareNumber，不做移动  
26.               
27.             while(array[j]>compareNumber&&i<j){  
28.                 j--;  
29.             }             
30.               
31.             if(i>=j){  
32.                 if(array[j]>compareNumber){  
33.                     middlePosition = j;  
34.                 }else{  
35.                     middlePosition = (j+1);  
36.                 }  
37.                 break;  
38.             }  
39.             //从数组首端开始迭代，得到大于compareNumber的数array[i]，此时从尾端迭代直至得到<=compareNumber的数  
40.             //array[j],交换这两个数的位置，然后继续迭代  
41.             swap(array,i,j);  
42.         }  
43.         //递归排序  
44.         quickSort(array,start,middlePosition-1);  
45.         quickSort(array,middlePosition,end);  
46.     }  

Java代码  

1. public static void swap(Object[] array,int a,int b){  
2.     Object temp = array[a];  
3.     array[a] = array[b];  
4.     array[b] = temp;  
5. }