Coursera普林斯顿大学公开课Algorithm I总结：排序算法
排序算法是将无序的数据化为有序数据的一种算法，排序算法应用十分广泛，有时候还是构成其他算法的基础，因此得到了广泛地研究。在教科书中比较流行的排序算法有：选择排序、插入排序、Shell排序、归并排序、快速排序、堆排序。
目录1 选择排序2 插入排序3 Shell排序4 归并排序5 快速排序6 结束语
选择排序
选择排序的思想非常简单：
在第i次循环中，在剩余元素中找到最小元素的下标min
交换a[i]和a[min]
比如下图，红色箭头所指的就是i的位置，向右找到最小元素的下标，也就是蓝色箭头所指的位置，然后交换两个元素的位置
插入排序
插入排序的过程有点像我们打牌的时候给扑克牌排序，从左到右遍历元素，对于每个元素，将其插入到左边排好序序列的合适位置，实际实现的时候是将当前元素与其左边的元素不断交换，直到遇到左边元素比当前元素小或者当前已经处于数组最左边的情况。
比如下图中的当前元素3被插入到合适的位置（2、4之间）
选择排序的复杂度总是O(n^2)，而插入排序虽然最坏情况下复杂度也是O(n^2)，但是对于基本排好序的序列进行排序时，它的复杂度是O(n)。
Shell排序
Shell排序可以算是插入排序的一个扩展。插入排序中的元素交换操作都是对相邻的元素进行，而交换相邻元素，只能使得数列的逆序对减少1。于是Shell排序实际上是首先确定一个递减序列h，首先进行步长为h[0]的插入排序，然后进行h[1]的插入排序……最后进行1的插入排序。
步长为4的插入排序排好序的序列，完成之后，对于所有的a[i]和a[i+4]满足a[i]<a[i+4]。
依次进行13、4、1排序的序列，最终完成之后，整个序列都是有序的了。
进行步长为3的插入排序的过程：
Shell排序实际上使用了两点来提高排序的效率：
大步长时子序列较小
小步长时序列基本上已经排好序，因此插入排序效率较高
Shell排序的复杂度取决与步长的序列，可以证明，用3x+1步长序列（ 1, 4, 13, 40, 121, 364, ...）的时候复杂度为O(n^{3/2})。
归并排序
归并排序的应用十分广泛，基本上许多编程语言的内置稳定排序就是用的归并排序。
归并排序的基本过程如下：
将数组分成左右两半
递归地将左右两半数组各自排好序
将左右两半各自有序的数组合并成整体有序的数组
最后合并的时候应该怎么合并呢？其实有点类似于选择排序，也是每次选出两个数组剩余元素中最小的元素，不同的是，由于两个数组都是排好序的，所以最小元素只能是两个数组最左边的元素之一。具体代码如下，要合并的是数组a中lo~mi和mi+1~hi两段，首先将数组所有元素复制到一个数组aux中，然后进行合并。
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)
{
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
然后整个算法的实现就非常简单了：
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
关于归并排序的算法复杂度，由于每次将原来规模为N的问题分成两个规模为N/2的子问题，然后合并的复杂度是O(N)，整体的复杂度可以用以下递推式D(N)=2D(N/2)+N来表示，根据这个递推式主定理告诉我们，它的时间复杂度是O(N\lg N)。其实也可以从下面的一张图很容易地看出算法的复杂度，每层都是N，总共有\lg N层，所以总体复杂度为O(N\lg N)
空间复杂度方面，归并排序需要额外长度为N的数组来进行归并。
归并排序具体实现的时候，可以用下面的方法来加速：
对小的子数组用插入排序来代替归并排序
如果左边子数组的最后元素小于右边子数组的第一个元素，则无需归并
通过不断地切换aux和a的地位，避免每次都将数据复制到aux数组然后再进行归并。
归并排序除了采用自顶向下采用递归不断拆分问题外，也可以采用自底向上的形式，自底向上的归并排序采用以下过程：
遍历数组，归并长度为1的子数组
对长度的2、4、6、8……的子数组重复上面一步
代码为：
public static void sort(Comparable[] a)
{
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
快速排序
快速排序的特点就是“快”，因此许多语言标准库的排序算法实现就是快速排序。快速排序还被评为二十世纪最伟大的十大算法之一，足见其重要性。
和归并排序一样，快速排序也是基于分治的思想的，它的基本思路是：
随机打乱数组
划分数组，使得对于下标j满足：
a[j](pivot)处于正确的位置
在下标j左边的元素都小于等于a[j]
在下标j右边的元素都大于等于a[j]
递归地为j左右两边的数组片段排好序
划分数组的方法是维护两个下标i、j：
递增下标i直到条件(a[i]<a[lo])不满足
递减下标j直到条件(a[j]>a[lo])不满足
交换a[i]和a[j]
代码为
// partition the subarray a[lo .. hi] by returning an index j
// so that a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j) break;
exch(a, i, j);
}
// put v = a[j] into position
exch(a, lo, j);
// with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
下面是算法执行前，算法执行中和算法执行后的示意图：
快排的平均复杂度是O(N\lg N)，并且它不像归并排序那样需要很多数据移动，所以在实际应用上会比较快。然而它的最坏情况复杂度是O(N^2)（对于拆分极度不平衡的情况），许多教科书上的实现对于没打乱过的顺序或者逆序的数组，以及即使打乱了的包含很多重复元素的数组，复杂度都会退化到O(N^2)。另外快排还有几个特点是：它只需要O(1)的额外空间，并且它是不稳定的排序。
在实际的实现上，快排有几个优化。一个是排序的子数组长度较短时，采用插入排序进行排序，二是采用数组头部、尾部、中间元素的中位数作为pivot，然后进行划分数组的操作。
上面提到在重复元素很多的情况下，如果不注意很容易会出现划分不平衡的情况，从而造成复杂度退化到O(N^2)。上面实现的代码中由于每次遇到跟pivot相同的元素时都会停止扫描，不会造成划分不平衡的情况。不过一个更好的做法是把与pivot相等的元素都放到正确的位置，这就是Dijkstra大神提出的3路划分的方法。
3路划分的目标是将数组分成3个部分：
lt和gt之间的元素是等于分割元素v
lt左边的元素都小于v
gt右边的元素都大于v
具体进行划分的方法如下，令v为进行划分pivot元素a[lo], 从左到右扫描：
若a[i] < v：交换a[lt]和a[i]，lt和i都加一
若a[i] > v：交换a[gt]和a[i]，gt减一
若a[i] == v： i加一
代码实现：
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
assert isSorted(a);
}
// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1);
sort(a, gt+1, hi);
assert isSorted(a, lo, hi);
}
3路快排的优势在于，如果数组中只包含常数种不同元素，排序的时间复杂度就是线性的。
结束语
其实排序算法领域是一个大坑，所涉及的内容非常非常多，即使到现在，仍然有相关的论文得到发表，这里只是提了几中排序的算法，包括应用、外部排序、并行排序等的内容都没有提，有空再补吧。
另外据说C++中sort实现是一种融合了堆排序和快速排序的叫做Introsort的东西，python中排序的实现是一种timsort的东西，决定有空研究下。
对排序有兴趣的童鞋可以看下wikipedia的链接：http://en.wikipedia.org/wiki/Sorting_algorithm，上面详尽地列出了各种排序算法。
最后附上公开课的课件以及本文各种排序算法的完整代码：
排序算法课件（2.1-2.3）
各种排序算法的代码（sorting部分）
原文链接：http://bimania.org/2012/10/23/coursera-algo-1-sorting/
目录1 选择排序2 插入排序3 Shell排序4 归并排序5 快速排序6 结束语
选择排序
选择排序的思想非常简单：
在第i次循环中，在剩余元素中找到最小元素的下标min
交换a[i]和a[min]
比如下图，红色箭头所指的就是i的位置，向右找到最小元素的下标，也就是蓝色箭头所指的位置，然后交换两个元素的位置
插入排序
插入排序的过程有点像我们打牌的时候给扑克牌排序，从左到右遍历元素，对于每个元素，将其插入到左边排好序序列的合适位置，实际实现的时候是将当前元素与其左边的元素不断交换，直到遇到左边元素比当前元素小或者当前已经处于数组最左边的情况。
比如下图中的当前元素3被插入到合适的位置（2、4之间）
选择排序的复杂度总是O(n^2)，而插入排序虽然最坏情况下复杂度也是O(n^2)，但是对于基本排好序的序列进行排序时，它的复杂度是O(n)。
Shell排序
Shell排序可以算是插入排序的一个扩展。插入排序中的元素交换操作都是对相邻的元素进行，而交换相邻元素，只能使得数列的逆序对减少1。于是Shell排序实际上是首先确定一个递减序列h，首先进行步长为h[0]的插入排序，然后进行h[1]的插入排序……最后进行1的插入排序。
步长为4的插入排序排好序的序列，完成之后，对于所有的a[i]和a[i+4]满足a[i]<a[i+4]。
依次进行13、4、1排序的序列，最终完成之后，整个序列都是有序的了。
进行步长为3的插入排序的过程：
Shell排序实际上使用了两点来提高排序的效率：
大步长时子序列较小
小步长时序列基本上已经排好序，因此插入排序效率较高
Shell排序的复杂度取决与步长的序列，可以证明，用3x+1步长序列（ 1, 4, 13, 40, 121, 364, ...）的时候复杂度为O(n^{3/2})。
归并排序
归并排序的应用十分广泛，基本上许多编程语言的内置稳定排序就是用的归并排序。
归并排序的基本过程如下：
将数组分成左右两半
递归地将左右两半数组各自排好序
将左右两半各自有序的数组合并成整体有序的数组
最后合并的时候应该怎么合并呢？其实有点类似于选择排序，也是每次选出两个数组剩余元素中最小的元素，不同的是，由于两个数组都是排好序的，所以最小元素只能是两个数组最左边的元素之一。具体代码如下，要合并的是数组a中lo~mi和mi+1~hi两段，首先将数组所有元素复制到一个数组aux中，然后进行合并。
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)
{
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
然后整个算法的实现就非常简单了：
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
关于归并排序的算法复杂度，由于每次将原来规模为N的问题分成两个规模为N/2的子问题，然后合并的复杂度是O(N)，整体的复杂度可以用以下递推式D(N)=2D(N/2)+N来表示，根据这个递推式主定理告诉我们，它的时间复杂度是O(N\lg N)。其实也可以从下面的一张图很容易地看出算法的复杂度，每层都是N，总共有\lg N层，所以总体复杂度为O(N\lg N)
空间复杂度方面，归并排序需要额外长度为N的数组来进行归并。
归并排序具体实现的时候，可以用下面的方法来加速：
对小的子数组用插入排序来代替归并排序
如果左边子数组的最后元素小于右边子数组的第一个元素，则无需归并
通过不断地切换aux和a的地位，避免每次都将数据复制到aux数组然后再进行归并。
归并排序除了采用自顶向下采用递归不断拆分问题外，也可以采用自底向上的形式，自底向上的归并排序采用以下过程：
遍历数组，归并长度为1的子数组
对长度的2、4、6、8……的子数组重复上面一步
代码为：
public static void sort(Comparable[] a)
{
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
快速排序
快速排序的特点就是“快”，因此许多语言标准库的排序算法实现就是快速排序。快速排序还被评为二十世纪最伟大的十大算法之一，足见其重要性。
和归并排序一样，快速排序也是基于分治的思想的，它的基本思路是：
随机打乱数组
划分数组，使得对于下标j满足：
a[j](pivot)处于正确的位置
在下标j左边的元素都小于等于a[j]
在下标j右边的元素都大于等于a[j]
递归地为j左右两边的数组片段排好序
划分数组的方法是维护两个下标i、j：
递增下标i直到条件(a[i]<a[lo])不满足
递减下标j直到条件(a[j]>a[lo])不满足
交换a[i]和a[j]
代码为
// partition the subarray a[lo .. hi] by returning an index j
// so that a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j) break;
exch(a, i, j);
}
// put v = a[j] into position
exch(a, lo, j);
// with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
下面是算法执行前，算法执行中和算法执行后的示意图：
快排的平均复杂度是O(N\lg N)，并且它不像归并排序那样需要很多数据移动，所以在实际应用上会比较快。然而它的最坏情况复杂度是O(N^2)（对于拆分极度不平衡的情况），许多教科书上的实现对于没打乱过的顺序或者逆序的数组，以及即使打乱了的包含很多重复元素的数组，复杂度都会退化到O(N^2)。另外快排还有几个特点是：它只需要O(1)的额外空间，并且它是不稳定的排序。
在实际的实现上，快排有几个优化。一个是排序的子数组长度较短时，采用插入排序进行排序，二是采用数组头部、尾部、中间元素的中位数作为pivot，然后进行划分数组的操作。
上面提到在重复元素很多的情况下，如果不注意很容易会出现划分不平衡的情况，从而造成复杂度退化到O(N^2)。上面实现的代码中由于每次遇到跟pivot相同的元素时都会停止扫描，不会造成划分不平衡的情况。不过一个更好的做法是把与pivot相等的元素都放到正确的位置，这就是Dijkstra大神提出的3路划分的方法。
3路划分的目标是将数组分成3个部分：
lt和gt之间的元素是等于分割元素v
lt左边的元素都小于v
gt右边的元素都大于v
具体进行划分的方法如下，令v为进行划分pivot元素a[lo], 从左到右扫描：
若a[i] < v：交换a[lt]和a[i]，lt和i都加一
若a[i] > v：交换a[gt]和a[i]，gt减一
若a[i] == v： i加一
代码实现：
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
assert isSorted(a);
}
// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1);
sort(a, gt+1, hi);
assert isSorted(a, lo, hi);
}
3路快排的优势在于，如果数组中只包含常数种不同元素，排序的时间复杂度就是线性的。
结束语
其实排序算法领域是一个大坑，所涉及的内容非常非常多，即使到现在，仍然有相关的论文得到发表，这里只是提了几中排序的算法，包括应用、外部排序、并行排序等的内容都没有提，有空再补吧。
另外据说C++中sort实现是一种融合了堆排序和快速排序的叫做Introsort的东西，python中排序的实现是一种timsort的东西，决定有空研究下。
对排序有兴趣的童鞋可以看下wikipedia的链接：http://en.wikipedia.org/wiki/Sorting_algorithm，上面详尽地列出了各种排序算法。
最后附上公开课的课件以及本文各种排序算法的完整代码：
排序算法课件（2.1-2.3）
各种排序算法的代码（sorting部分）
原文链接：http://bimania.org/2012/10/23/coursera-algo-1-sorting/
