快速排序-二切快排

快速排序

二切快排的思想: 取数组的第一个元素为切分元素,左边子数组全部小于等于切分元素，右边子数组全部大于等于切分元素，这样每切分一次就可以确定一个元素的位置。左右子数组再分别递归排序。

伪代码实现

 1   public static void main(String[] args) {
 2         int[] a = new int[8];
 3         sort(a,0,a.length-1);
 4 
 5 
 6 
 7     }
 8 
 9 
10     public void sort(int[] a,int lo,int hi){
11         int j = partition(a,lo,hi);
12         sort(a,lo,j-1);
13         sort(a,j+1,hi);
14     }
15 
16     public int partition(int[] a,int lo,int hi){
17         int i = lo;
18         int j = hi+1;
19         int v = a[lo];
20         while(true){
21 
22             while(a[++i]<=v){
23                 if(i==hi){
24                     break;
25                 }
26             }
27             while(a[--j]>=v){
28                 if(j==lo){
29                     break;
30                 }
31             }
32 
33             if(i>=j){
34                 break;
35             }
36             exchange(a,i,j);
37 
38 
39         }
40         exchange(a,lo,j);
41 
42 
43         return 0;
44     }