算法笔记－排序02:归并排序,快速排序
思路
归并排序的思想是先将数组分散为小数组分别排序，然后将结果归并起来。
原地归并的抽象方法
将两个已经排序好的数组归并为一个数组这一操作对于归并排序的意义不言而喻，以下是归并方法的实现：
public static void merge(Comparable[] a, int low, int mid, int high){
int i = low, j = mid+1;
for (int k = low; k <= high; k++)
indexA[k] = a[k];
for (int k = low; k <= high; k++){
if (i > mid) a[k] = indexA[j++];
else if (j > high) a[k] = indexA[i++];
else if (less(indexA[j], indexA[i])) a[k] = indexA[j++];
else a[k] = indexA[i++];
}
}
自顶向下的归并排序
基于原地归并的抽象方法实现了另一种递归归并，这是应用高效算法设计中分治思想的典型例子：
public class Merge {
private static Comparable[] indexA;
public static void merge(Comparable[] a, int low, int mid, int high){
int i = low, j = mid+1;
for (int k = low; k <= high; k++)
indexA[k] = a[k];
for (int k = low; k <= high; k++){
if (i > mid) a[k] = indexA[j++];
else if (j > high) a[k] = indexA[i++];
else if (less(indexA[j], indexA[i])) a[k] = indexA[j++];
else a[k] = indexA[i++];
}
}
public static void sort(Comparable[] a, int low, int high){
if (indexA==null) indexA = new Comparable[a.length];
if (high <= low) return;
int mid = low + (high-low)/2;
sort(a, low, mid);
sort(a, mid+1, high);
merge(a, low, mid, high);
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
在实际运用中，希尔排序和归并排序的运行时间之差在常数范围内
运行时间
自底向上的归并排序
实现归并排序的另一种方式是从小数组开始归并：首先我们将数组的每一个元素都当做一个只有一个元素的数组，然后将其两两归并。然后我们将整个数组的每两个元素都当做一个小数组，然后将其两两归并，然后四个四个归并，依次类推，直到最后归并成一个大数组，排序就完成了。
完整实现代码如下：
public class MergeBU {
private static Comparable[] indexA;
public static void merge(Comparable[] a, int low, int mid, int high){
int i = low, j = mid+1;
for (int k = low; k <= high; k++)
indexA[k] = a[k];
for (int k = low; k <= high; k++){
if (i > mid) a[k] = indexA[j++];
else if (j > high) a[k] = indexA[i++];
else if (less(indexA[j], indexA[i])) a[k] = indexA[j++];
else a[k] = indexA[i++];
}
}
public static void sort(Comparable[] a){
if (indexA == null) indexA = new Comparable[a.length];
for (int sz = 1; sz<a.length; sz = sz+sz)
for (int low = 0; low < a.length-sz; low += sz+sz)
merge(a,low,low+sz-1,Math.min(low+sz+sz-1, a.length-1));
}
public static void main(String[] args){
Integer[] a = {9,8,7,6,5,4,3,2,1};
sort(a);
for (Integer i: a){
System.out.println(i);
}
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
两种实现方式的速度比较(给一千个大小为一万的数组排序)：
运行结果
快速排序
快速排序可能是应用的最为广泛的一种算法，它流行的原因是实现简单，适用于各种不同的输入数据且在一般的应用中比其他排序算法都要快的多。快速排序的优点：
是原地排序（只需要一个很小的辅助栈）。
所需时间跟NlgN成正比。
快速排序思路：
快速排序和归并排序是互补的，归并排序将整个数组分成小数组，然后将排好序的小数组归并以将整个数组排序；而快速排序是在将大数组分成小数组的时候排序，当小数组小到不可再分的时候，排序也就完成了。
1.首先选择一个中间元素（一般选左端或者右端）。
2.分别获取除中间元素外的左右两端的索引。
3.由左右两端逐渐向中间迭代，每迭代一步比较一下索引中的元素和中间元素，当左边出现比中间元素大的元素的时候，暂停左边的迭代，当右边迭代出比中间元素小的元素的时候，右边迭代也暂停，交换左右两边的元素。
4.重复步骤3，直到左右两边的索引相遇，然后将中间元素移动到中间，这时中间元素左边的元素都比它小，右边的元素都比它大。
5.将上面的中间元素左右两边当成两个数组，分别进行上述过程。
6.重复以上步骤直到数组不可再分。
完整代码
public class Quick {
public static void sort(Comparable[] a){
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a,int low, int high){
if (high <= low) return;
int j = partition(a,low,high);
sort(a,low,j-1);
sort(a,j+1,high);
}
private static int partition(Comparable[] a, int low, int high){
//将数组切分为a[lo..i-1], a[i], a[i+1..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); //将v = a[j]放入正确位置
return j; //a[lo..j-1] <= a[j] <= a[j+1..hi]达成
}
public static void main(String[] args){
Integer[] a = {9,8,7,6,5,4,3,2,1};
sort(a, 0, a.length-1);
for (Integer i: a){
System.out.println(i);
}
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
比较快速排序和归并排序的速度
命令：
% java Main Merge Quick 10000 1000
运行结果
快速排序算法的改进
快速排序自被C.A.R Hoare在1960年发明后，就不断的有人试图改进它，但是由于快速排序已经“so well-balanced”，改进所带来的优化往往都被副作用抵消了，比如《算法》一书中对快速排序的实现中在排序之前会先随机打乱数组来避免一种极端情况——当我们每一次选择的中间元素都恰好是最小元素时，该算法会变的像选择排序，从而导致时间复杂度变成N的平方。但是笔者在测试的时候发现运行上面的指令时随机打乱数组所花掉的时间几乎使得运行时间加倍，而事实上出现这种极端情况的概率比你的电脑在排序时突然被闪电击中的概率都要小的多(这个flag不是我立的,我以后不随随便便排序了)。
但是依然有人找到了一些有用的改进方式：
1.第一种改进方案是说由于插入排序在小数组的时候会比快速排序快，所以在分成小数组的时候使用插入排序，然而笔者在自己的电脑上测试的时候发现无论是大数组还是小数组，快速排序都比插入排序要快得多，按照这种方式修改的快速排序也变慢了，所以存疑。
2.实际应用中我们排序的数组常常含有大量的重复元素，例如将上千万人员的资料按照生日排序，那就必然会有大量的重复的数值(毕竟一百年里面也就四万多天，分配给上千万人作生日，自然有大量重复)，于是有人提出与其将数组二分，不如分成三部分，一部分小于中间值，一部分大于中间值，一部分等于中间值，此算法被称为三向切分的快速排序，以下是代码：
public class Quick3Way {
public static void sort(Comparable[] a){
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a,int low, int high){
if (high <= low) return;
int lt = low, i = low+1,gt = high;
Comparable v = a[low];
while (i <= gt){
int cmp = a[i].compareTo(v);
if (cmp < 0)exchange(a,lt++,i++);
else if (cmp > 0)exchange(a,i,gt--);
else i++;
}
sort(a,low,lt-1);
if (gt<high) sort(a,gt+1,high);
}
public static void main(String[] args){
Integer[] a = {9,8,7,6,5,4,3,2,1};
sort(a, 0, a.length-1);
for (Integer i: a){
System.out.println(i);
}
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
当使用随机生成的由0～100组成的大小为一万的数组排序一千次时改进方法与原方法所花费的时间如下：
运行结果
对于标准的快速排序，随着数组规模的增大其运行时间会趋于平均运行时间，大幅度偏离的情况非常罕见。而三向切分的快速排序对于大量重复元素的数组来说运行时间由线性对数级别降低到了线性级别，并且和元素的排列没有关系。由于在平常使用中对含有大量重复元素的数组排序的情况很常见，所以拥有对重复元素的适应性的三向分切的快速排序成为了排序库函数的最佳选择。
经过精心优化的快速排序在绝大多数计算机的绝大多数应用中都比其他算法要快，它在当前业界的广泛使用正说明了这一点。
总结一下当前学习过的排序算法的速度：
在给千万级别的数组排序的情况下：
Quick > Merge > Shell > Insertion > Selection
资源以及参考
普林斯顿大学算法课程以其教材《算法》第四版
