總結(jié)：快速排序大體上也是用的歸并的思想澡腾，與歸并排序不同的是它通過切分確定某一個元素的最終位置并且將較大的數(shù)和較小的數(shù)分開了，然后按照這個位置切分糕珊，快速排序算法的時間復(fù)雜度為O(nlgn),在處理大型數(shù)據(jù)的時候效率比歸并算法要高动分，而且改進(jìn)后的三向切分的快速排序處理重復(fù)元素較多的數(shù)據(jù)時，時間復(fù)雜度可以接近O(n).
快速排序
主要思想：分治法
/*
* 快速排序
* 基本思想：找到元素在亂序序列中的位置
*/
public static void quickShort(Comparable[] a){
quickShort(a, 0, a.length-1);
}
public static void quickShort(Comparable[] a,int lo,int hi){
if(lo>=hi) return;//if(lo+5>=hi) Insertion(a);改進(jìn)如果要排序的數(shù)組小于5红选，就轉(zhuǎn)換成插入排序
int j = partition(a,lo,hi);//切分?jǐn)?shù)組
quickShort(a,lo,j-1);//對前半部分排序
quickShort(a,j+1,hi);//對后半部分排序
}
private static int partition(Comparable[] a, int lo, int hi) {
// TODO Auto-generated method stub
int i = lo,j=hi+1;
Comparable v = a[lo];
while(true){
while(less(a[++i],v)) if(i==hi) break;//從左向右找到第一個比v小的數(shù)
while(less(v,a[--j])) if(j==lo) break;//從右向左找到第一個比v大的數(shù)
if(i>=j) break;
exch(a, i, j);//將比v大的數(shù)和比v小的數(shù)交換
}
exch(a,lo,j);
return j;
}
三向切分的快速排序
改進(jìn)項(xiàng)：在切分時分成三部分
/*
* 三向切分的快速排序
* 基本思想：在切分時分成三部分
*/
private static void quick3Short(Comparable[] a,int lo,int hi){
if(hi<=lo) return;
int lt = lo,i = lo+1,gt = hi;
Comparable v = a[lo];
while(i<=gt){
int cmp = a[i].compareTo(v);
if(cmp<0) exch(a,lt++,i++);
if(cmp>0) exch(a,gt--,i);
else i++;
}
quick3Short(a, lo, lt-1);
quick3Short(a, gt+1, hi);
}
