《算法导论的Java兑现》 8 快速排序
日期：2014-05-20 浏览次数：21075 次
《算法导论的Java实现》 8 快速排序
Blog地址：
《算法导论的Java实现》 8 快速排序
8 快速排序
8.1 对快速排序的描述
快速排序是基于“分治算法”的。在《1.3.1 分治算法》里面已经介绍过的，就不重复讲了。只要记住基于“分治”的算法，一般都是主函数是个“分治”语句（if…else…）,分治块里面一般是调用本身的递归。
伪代码：
Java代码：
输出：
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代码：
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 < r 2 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);
}
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
