黑马程序员技术交流社区

标题: 快排算法怎么写？ [打印本页]

---

作者: 微--尘    时间: 2016-7-5 00:36
标题: 快排算法怎么写？
快排算法怎么写？

---

作者: hlhdidi    时间: 2016-7-5 19:02

1. public class Quick {
   
2.     public static void sort(Comparable[] a) {
   
3.         StdRandom.shuffle(a);
   
4.         sort(a,0,a.length-1);
   
5.     }
   
6. 
   
7.     public static void sort(Comparable[] a, int lo, int hi) {
   
8.         if(hi<=lo) return;
   
9.         int j=partition(a,lo,hi);    //j前的元素不大于a[j],j后的元素不小于a[j]
   
10.         sort(a,lo,j-1);
    
11.         sort(a,j+1,hi);
    
12.     }
    
13. 
    
14.     public static int partition(Comparable[] a, int lo, int hi) {
    
15.         int i=lo;
    
16.         int j=hi;
    
17.         Comparable v=a[lo];
    
18.         while(true) {
    
19.             while(less(a[++i],v)) {if(i==hi) break;}
    
20.             while(less(v,a[--j])) {if(j==lo) break;}
    
21.             if(i>=j) break;
    
22.             exch(a,i,j);
    
23.         }
    
24.         exch(a,lo,j);
    
25.         return j;
    
26.     }
    
27.     public static void exch(Comparable[] a, int i, int min) {
    
28.         Comparable t=a[i];
    
29.         a[i]=a[min];
    
30.         a[min]=t;
    
31.     }
    
32.     public static boolean less(Comparable v, Comparable w) {
    
33.         return v.compareTo(w)<0;
    
34.     }
    
35. }

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2