GuangchaoSun's Blog

2.3 Quicksort

发表于  |    |   分类于   |  

快速排序是应用最广泛的排序算法
优点：

  • 原地排序（只需要一个很小的辅助栈）
  • 长度为N的数组排序所时间和NlgN成正比

但需要非常小心才能避免低劣的性能。
Quick Sort is a divide-and-conquer method for sorting.
递归调用发生在处理整个数组之后，切分（partition）的位置取决于数据组的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Quick{
	public static void sort(Comparable[] a)
	{
		StdRandom.shuffle(a);//消除对依赖的输入
		sort(a,0,a.length-1);
	}
	public static void sort(Comparable[] a,int lo,int hi)
	{
		if(hi<lo) return;
		int  j = portation(a,lo,hi);//切分
		sort(a,lo,j-1);//将左半部分排序
		sort(a,j+1,hi);//将右半部分排序
	}
}

切分（portition）需要满足三个条件：

  • 对于某个j，a[j]已经排定
  • a[lo]到a[j-1]的所有元素都不大于a[j]
  • a[j+1]到a[hi]的所有元素都不小于a[j]

快速排序的切分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 == lo) break;
		while(less(v,a[--j])) if(i == hi) break;
		if(i >= j) break;
		exch(a,i,j);
	}
	exch(a,lo,j);//将v = a[j]放入正确的位置
	return j;//a[lo..j-1] <= a[j] <= a[j+1..hi]达成
}

具体的思路是：随意地取a[lo]为切分元素，然后从数组的左端开始扫描直到找到一个大于等于他的元素，再从右端开始扫描，直到找到一个小于等于他的元素。我们交换这两个元素的位置。
快速排序的缺点：在切分不平衡时程序可能会极为低效。

三向切分的快速排序：

应用场景：如果出现有大量重复的数组，这时候就需要用到三向切分的快速排序。
使用Comparable接口（而非less()）对a[i]进行三向比较来直接处理以下三种情况：

  • a[i]小于v，将a[lt]和a[i]交换，将lt和i加一；
  • a[i]大于v，将a[gt]和a[i]交换，将gt减一；
  • a[i]等于v，将i加一；

下面为代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Quick3way{
	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) ecah(a, i, gt--);
			else i++;
		}//现在a[lo..lt-1] < V =a[lt..gt] < a[gt..hi]成立
		sort(a, lo, lt - 1);
		sort(a, gt + 1, hi);
	}
}

Exercise

  1. Write a program Sort2distinct.java that sorts an array that is known to contain just two distinct key values.
  2. About how many compares will Quick.sort() make when sorting an array of N items that are all equal?
    Solution. ~ N lg N compares. Each partition will divide the array in half, plus or minus one.
  3. Show, in the style of the trace given with the code, how the entropy-optimal sort first partitions the array B A B A B A B A C A D A B R A.