《算法导论的Java实现》 8 快速排序

Blog地址：
《算法导论的Java实现》 8 快速排序

8 快速排序

8.1 对快速排序的描述

快速排序是基于“分治算法”的。在《1.3.1 分治算法》里面已经介绍过的，就不重复讲了。只要记住基于“分治”的算法，一般都是主函数是个“分治”语句（if…else…）,分治块里面一般是调用本身的递归。

伪代码：

QUICKSORT(A, p, r)
 if p < r
    then q ← PARTITION(A, p, r)
         QUICKSORT(A, p, q - 1)
         QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
  x ← A[r]
  i ← p - 1
  for j ← p to r - 1
       do if A[j] ≤ x
             then i ← i + 1
                  exchange A[i] ←→ A[j]
  exchange A[i + 1] ←→ A[r]
  return i + 1

Java代码：

import java.util.Comparator;

public class QuickSort {
	public static <T> void quickSort(T[] a, Comparator<? super T> c) {
		quickSort(a, c, 0, a.length);
	}

	public static <T> void quickSort(T[] a, Comparator<? super T> c, int p,
			int r) {
		if (p < r) {
			int q = partition(a, c, p, r);
			quickSort(a, c, p, q);
			quickSort(a, c, q + 1, r);
		}
	}

	public static <T> int partition(T[] a, Comparator<? super T> c, int p, int r) {
		T t = a[r - 1];
		int i = p - 1;
		for (int j = p; j < r - 1; j++) {
			if (c.compare(a[j], t) <= 0) {
				i++;
				T tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}

		T tmp = a[i + 1];
		a[i + 1] = a[r - 1];
		a[r - 1] = tmp;
		return i + 1;
	}

	public static void main(String[] args) {
		Integer[] temp = new Integer[] { 2, 8, 7, 1, 3, 5, 6, 4 };
		quickSort(temp, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});

		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

输出：
1 2 3 4 5 6 7 8 


code后感
快速排序已经被讨论得太多。所以，反而没有什么可写的了。PARTITION函数如何对子数组进行划分，在《算法导论》里面说得也很清楚。
值得玩味的是，《算法导论》第一版里面的伪代码用while来做循环，第二版是for来循环。伪代码我是照英文版第二版来的，所以，包括Java代码都用for来循环了。我没看出效率上两者有什么区别。
但是可读性上，while做循环的程序，就像一直以来的教科书上的样子,i和j像2个指针不断往中间靠，直到重叠在一起。似乎，可以使快速排序更容易理解一点。

细心的人，还会注意到下面的不同：
伪代码：QUICKSORT(A, p, q - 1)
我的Java代码：quickSort(a, c, p, q);
也就是，分治时，边界不同。为什么会这样？说起来有点搞。
事实上，第一版的伪代码就是：QUICKSORT(A, p, q)。是不是第二版的伪代码出错了呢？这点我也没有仔细分析。quickSort(a, c, p, q)配合for循环的PARTITION函数，再考虑到数组下标的边界情况，我的代码可以正常运行。更细的研究，没有太大的必要，都是一些加一减一的问题了。



8.3 快速排序的随机化版本
8.2 快速排序的性能一节里面，没有伪代码，被我跳过。但是，里面讲到快速排序的最坏情况，会退化成Θ(n^2)，类似于冒泡插入等排序了。为了不依赖于样本（被排序的原始序列），PARTITION执行前追加一步随机处理，就是将p到r之间随机抽取一个值i，交换A[r]和A[i]。


伪代码：

RANDOMIZED-PARTITION(A, p, r)
1  i ← RANDOM(p, r)
2  exchange A[r] ↔ A[i]
3  return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2     then q ← RANDOMIZED-PARTITION(A, p, r)
3          RANDOMIZED-QUICKSORT(A, p, q - 1)
4          RANDOMIZED-QUICKSORT(A, q + 1, r)

Java代码：

	public static <T> void randomizedQuickSort(T[] a, Comparator<? super T> c) {
		randomizedQuickSort(a, c, 0, a.length);
	}

	public static <T> void randomizedQuickSort(T[] a, Comparator<? super T> c,
			int p, int r) {
		if (p < r) {
			int q = randomizedPartition(a, c, p, r);
			randomizedQuickSort(a, c, p, q);
			randomizedQuickSort(a, c, q + 1, r);
		}
	}

	public static <T> int randomizedPartition(T[] a, Comparator<? super T> c,
			int p, int r) {
		int i = new Random().nextInt(r - p) + p;
		T tmp = a[i];
		a[i] = a[r - 1];
		a[r - 1] = tmp;
		return partition(a, c, p, r);
	}

测试代码：

	public static void main(String[] args) {
		Integer[] temp = new Integer[] { 2, 8, 7, 1, 3, 5, 6, 4 };

		randomizedQuickSort(temp, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});

		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

输出：
1 2 3 4 5 6 7 8 

code后感
随机化版本本身没有什么好说的，快速排序的变种之一。
但是变种的出现，是个有趣的话题。
《算法导论》通读后，如果你大部分都能搞懂了，那么我恭喜你，可以称为一个合格的程序员了。但是如果仅仅通读正文的话，那么我就很遗憾的告诉你，太可惜了，《算法导论》这本书就连习题部分都是很牛叉的。
比方说这里的STOOGE-SORT排序
伪代码：

1  if A[i] > A[j]
2     then exchange A[i] ↔ A[j]
3  if i + 1 ≥ j
4     then return
5  k ← ┕(j - i + 1)/3┙
6  STOOGE-SORT(A, i, j - k)
7  STOOGE-SORT(A, i + k, j)
8  STOOGE-SORT(A, i, j - k)

15 个解决方案

#1

顶贴为了学习

#2

这种帖子要顶。

#3

顶到出新篇

#4

学习下！！++

#5

顶到出新篇

#6

额？必须手动写快排吗？有系统快排吗？

#7

啊!你又复活咯! 来俺的群玩吧 注释写好 53596919

#8

引用 6 楼 kprf2009 的回复:

额？必须手动写快排吗？有系统快排吗？

如果你只想“知其然”的话，当然不用自己写。
java.util.Collections的sort函数可以满足大部分的要求。

我在前面讲分治算法时讲到，java.util.Collections的sort函数实际是调用了java.util.Arrays的sort(List)。
而java.util.Arrays的sort(List)里面主要是调用了mergeSort，也就是讲“分治算法”时，讲到的合并排序。
你说的系统快排也是有的，那就是Arrays的sort(int)，sort(long)等。
不过，那些快速排序更是变种得厉害，没有点基本功，有点难以看懂。

最后说一句，虽然有系统快排，不必手写，但是快排的随机化变种里的RANDOMIZED-PARTITION函数还是很用用的，在后面的章节，“以线性期望时间做选择（检索）”中被巧妙的用到了。

#9

引用 7 楼 bearkin 的回复:

啊!你又复活咯! 来俺的群玩吧 注释写好 53596919

。。。 俺不怎么上QQ的，所以。。。。。

#10

这样子啊 没关系

#11

引用 8 楼 chen09 的回复:

引用 6 楼 kprf2009 的回复:

额？必须手动写快排吗？有系统快排吗？


如果你只想“知其然”的话，当然不用自己写。
java.util.Collections的sort函数可以满足大部分的要求。

我在前面讲分治算法时讲到，java.util.Collections的sort函数实际是调用了java.util.Arrays的sort(List)。
而java.uti……

我表示各种排序我都会   只是觉得懒得写

手动快排  堆排  冒泡  插入  。。。

#12

引用 11 楼 kprf2009 的回复:

我在前面讲分治算法时讲到，java.util.Collections的sort函数实际是调用了java.util.Arrays的s……

呵呵，都会的话说明基本功扎实了。

#13

顶到出新篇

#14

顶到出新篇

#15

有重复数字就不对了