归并排序和希尔排序一般都比快速排序慢,其原因就在它们还在内循环中移动数据;快速排序的另一个速度优势在于它的比较次数很少。
快速排序的特点:
快速排序的切分:
切分满足下面三个条件:
private static int partition(Comparable[] a,int lo,int hi){
int i=lo,j=hi+1;
Comparable v = a[lo]; //子数组第一个元素作为切分元素
while(true){
while(less(a[++i],v)) if(i==hi) break; //从左到右找到第一个大于切分元素的元素
while(less(v,a[--j])) if(j==lo) break; //从右至左找到第一个小于切分元素的元素
if(i>=j)break;
exch(a,i,j); //交换找到的两个元素
}
exch(a,lo,j); //最后将切分元素交换到正确的位置
return j;
}
快速排序特点:
快速排序的实现需要注意几个细节:
public static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo)return ;
int j = partition(a,lo,hi); //切分
sort(a,lo,j-1); //递归左半部分排序
sort(a,j+1,hi); //递归右半部分排序
}
含有大量重复元素的数组,快速排序还有巨大的改进空间。一个经典的算法是Dijkstra的“三向切分的快速排序”。它从左到右遍历数组,设有三个指针lt,i,gt。使alo...lt-1中的元素都小于v,agt+1...hi中的元素都大于v,alt...i-1元素都等于v,ai...gt元素未定。
对于包含大量相同元素的数组,它将排序时间线性对数级别降到了线性级别。
private static void sort(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++); //小于,放左边
else if(cmp>0) exch(a,i,gt--); //大于,放右边
else i++; //等于,放中间
}
//只递归左右小于和大于V的部分,中间等于V的部分不需要递归
sort(a,lo,lt-1);
sort(a,gt+1,hi);
}
算法改进: