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

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

8 快速排序

8.1 对快速排序的描述

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

伪代码：

Java code

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代码：

Java code

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]。


伪代码：

Java code

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 < r2     then q ← RANDOMIZED-PARTITION(A, p, r)3          RANDOMIZED-QUICKSORT(A, p, q - 1)4          RANDOMIZED-QUICKSORT(A, q + 1, r)

Java代码：

Java code

    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);    } 
 

测试代码：

Java code

    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排序
伪代码：

Java code

1  if A[i] > A[j]2     then exchange A[i] ? A[j]3  if i + 1 ≥ j4     then return5  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)

[解决办法]

顶贴为了学习
[解决办法]
这种帖子要顶。
[解决办法]
学习下！！++
[解决办法]
额？必须手动写快排吗？有系统快排吗？

查看更多 下一篇