开始之前
后面会用到的静态函数
比较compare函数和交换exchange的函数以及随机打乱的shuffle函数:
private static int compare(Comparable v, Comparable w)
{
return v.compareTo(w);
}
private static void exchange(Comparable[] a, int i, int j)
{
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void shuffle(Object[] a)
{
Random random = new Random(System.currentTimeMillis());
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + random.nextInt(n-i);
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}将这些操作单独提出来作为单独的函数有利于排序算法代码的【可读性】，便于【理解】。
说明
Comparable[] a指一个实现了Comparable接口的类能够使用比较运算符比较元素的数组，实现了这个接口才能使用compareTo比较两个元素大小：
比如String字符串数组 String[] s 或者Integer数组 Integer[] i
shuffle函数是个随机打乱元素顺序的函数。
排序算法影响执行时间的主要操作是比较和交换；不进行比较的排序算法的主要操作则是访问数组的次数。
选择排序
找到数组中最小元素，将它与第一个元素交换位置；然后在剩下的元素中，找到【最小】元素，将它与第二个元素交换位置；这样直到整个数组都被排序。
选择排序因为不断选择剩余元素中的最小值得名
public class Selection {
public static void sort(Comparable[] a)
{ //将a[]按升序排列
int N = a.length;//数组长度
for (int i = 0; i < N; i++)
{ //将a[i]与a[i+1...N]中最小元素交换
int min = i; //记录最小值位置
for (int j = i + 1; j < N; j++) //将a[i]和a[i]后面没有排序的元素a[j]比较大小
if (compare(a[j], a[min] < 0) //compare() < 0 升序排序,compare() > 0 降序排序
min = j;
exchange(a, i, min);
}
}
}一个反列
这看上去是的代码量更小的插入排序。
实际上这个算法实际上就是冒泡排序，只不过是内循环的写法不同。
public class Selection {
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{ //将a[i]与a[i+1...N]中比a[i]小的元素交换
for (int j = i + 1; j < N; j++)
if (compare(a[j], a[i] < 0) //将a[]按升序排列
exchange(a, i, j);
}
}
}性能分析和特点
运行时间依赖输入与否：【不依赖】，无论是有序数组还是随机数组，排序的时间都一样长。
操作次数：选择排序大约需要N²/2比较和N次交换。
影响运行时间的操作：选择排序的花费主要花在在内循环中的【比较】上。
特点&使用范围：排序时的过程相当的直观，随着排序的进行，当前处理元素的左边的所有元素都是有序的。大部分的排序算法都没有这么直观。
注意：
最后一轮循环不需要做任何操作，可以不遍历。在外循环的判断条件可以改成
for (int i = 0; i < N-1; i++)，因为经过前N-1次的选择，除了最后一个元素，其他元素位置都排序好了。
插入排序
插入排序就是找到数组中一个位置，将待排序的元素插入已经排序的元素之间的一个适当【位置】。在插入前需要把其余所有元素向右移动一位，以便能腾出一个能插入位置。
这就像斗地主摸牌理牌那样，把一张牌插入左边刚好大于它，右边刚好小于它的位置，必须要把手牌往旁边移移留个空才能插进去。
易理解的简单算法
《算法 第四版》给出的原算法：
public class Insertion {
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 1; i < N; i++) //进行N-1次插入
{
for (int j = i; j > 0 && compare(a[j], a[j-1]) < 0; j--)
//将a[i]一直与前面的元素比较，调整插入位置
exchange(a, j, j-1);
}
}
}但是这个算法的实际运行时间实际要比选择排序还要长，因为交换过程的读取数组消耗了太多时间。
优化后可用的算法
去除交换步骤额外开销后的优化算法：
public class Insertion {
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 1; i < N; i++)
{
Comparable t = a[i];
int j;
for (j = i; j > 0 && less(t, a[j-1]); j--)
{ //将比t大的元素右移一格，当元素不再右移后就是要插入的位置
a[j] = a[j-1];
}
a[j] = t; //在腾出的空间放置待插入的元素
}
}
}性能分析和特点
运行时间依赖输入与否：【依赖】于输入元素的初始顺序，有序数组或接近有序的数组进行排序要比随机数组更快，主要是可以避免插入时移动元素次数过多。
操作次数：
插入排序最好情况下需要N-1次比较和0次交换，
最坏情况下大约需要N²/2比较和N²/2次交换，
平均情况下排序大约需要N²/4比较和N²/4次交换。
影响运行时间的操作：插入排序的花费主要花在【移动数组】上，也就是交换上。
特点&使用范围：插入排序对部分有序的数组十分高效，也适用于小规模数组。
希尔排序
希尔排序是基于【插入排序】实现的快速算法，只需要一点小的代码量改变，就可以让运行时间增长速度低于平方级。
希尔排序利用递增序列的数字作为固定的【间隔】，让这些【任意】固定间隔的元素都有序，这样可以大大减少插入移动元素的次数。
希尔排序的序列举例
比方说下面示范代码使用的函数的序列是1, 4, 13, 40, 121, ...，如果测试用的数组长度为15，
它会使用1，4，13三种间隔，
间隔为13时，a[0] a[13]构成一个数组使其有序；
间隔为4时：
a[0] a[4] a[8] a[12] 构成一个数组，使其有序
a[1] a[5] a[9] a[13] 构成一个数组，使其有序
a[2] a[6] a[10] a[14] 构成一个数组，使其有序
a[3] a[7] a[11]构成一个数组，使其有序；
间隔为1时就是插入排序；
最后会完成整个数组的排序，而前面间隔的排序减少了最后插入排序移动元素的次数。
public class Shell {
public static void sort(Comparable[] a)
{
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1)
{ //将数组变为间隔h有序
for (int i = h; i < N; i++)
{ //将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]...之中
for (int j = i; j >= h && compare(a[j], a[j-h]) < 0; j -= h)
exchange(a, j, j-h);
}
h = h/3;
}
}
}性能分析和特点
运行时间依赖输入与否：取决于规模，较小时和插入排序相差不大，较大时运行时间增速放缓，大致是n√n（n的根号下n）
操作次数：希尔排序的平均比较次数还是数学上【尚未解决】的难题。希尔排序的比较和交换次数取决于使用的递增序列，所给出的代码最坏比较次数是N的3/2次方。
影响运行时间的操作：已有研究表明，希尔排序中是最主要的操作是【比较】，而不是交换。
特点&使用范围：希尔排序适用于中等大小的数组，虽然运行速度达不到NlogN，但是可以接受。而且代码量很小，不需要额外的内存空间。
很多的论文研究给出了各种不同的递增序列，但还没有已证明的最好的递增序列。彻底理解希尔排序的性能是一项尚未解决的问题。有人通过大量的实验，给出了较好的结果：当规模较大时，比较和移动的次数约在n^1.25 到 (1.6n)^1.25 之间。
归并排序
归并排序的原理是利用分治思想将数组分成两半分别排序，然后将结果归并起来就是排序后的数组。归并排序的重点就如其名一样是指【归并】这一操作。
递归&归并
使用递归分成左右半边并排序很简单，但如何将递归后的数组归并成新【有序数组】却比较难。数组是按照大小对半切分的，递归到最后只有一个元素。
归并前过程中的两个数组虽然【各自】都有序，但直接合并【未必】是有序的。其中一边的数组元素未必都比另一边的【都要】小，反之亦然。如何将两个【已经排序】的数组合并成一个【有序】的数组，这是归并的重点。
原地归并的必要性
实现归并操作最简单的方法是每次归并过程中创建一个新数组，将结果归并回到这个数组中。但是这需要【额外】的空间开销，需要的空间为递归的深度和数组长度的乘积：NlogN。如果使用原地排序的方法可以只需要一个N的空间就可以归并结果。可以【节省】所需的空间。
private static void merge(Comparable[] a, int lo, int mid, int hi)
{ //将a[lo..mid]和a[mid+1..hi]归并
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) //将a[lo..hi]复制到aux[lo..hi]
aux[k] = a[k];
for (int k = lo; k <= hi; k++) //归并回到a[lo..hi]
if (i > mid) a[k] = aux[j++]; //如果左半边越界，说明左半边取完了，直接取右半边的元素归并a[]
else if (j > hi) a[k] = aux[i++]; //类似，右半边越界，右半边用尽，取左半边的元素
else if (compare(aux[j], aux[i]) < 0) a[k] = aux[j++]; //右半边的当前代取元素更小，将其归并回a[]中
else a[k] = aux[i++]; //反之，左半边的当前代取元素更小，将其归并回a[]中
}自顶向下的归并排序（递归）
public class Merge {
private static Comparable[] aux; //归并所需的辅助数组
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length]; //一次性分配空间
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return; //只有一个元素时
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
private static void merge(Comparable[] a, int lo, int mid, int hi)
{
//见上原地归并的方法
}
}自底向上的归并排序（迭代）
和自顶向下归并的【分治】方法不同，自底向上的归并会【多次】【遍历】整个数组。将【子数组】进行【两两归并】。子数组的大小sz初始时是1，每次加倍。
比如，首先是两两归并大小为1的数组，然后是四四归并大小为2的数组，然后是八八归并大小为4的数组，等等。
注意：
最后一次归并的第二个子数组可能比第一个子数组要小。最后一个子数组的大小只有在数组大小是sz的偶数倍时才会等于sz。
举例
比如有15个元素的数组：
第一次遍历，对子数组为1的数组两两归并，进行8次归并，归并后已排序的数组的子数组大小 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1；
第二次遍历，对子数组为2的数组四四归并，进行4次归并，归并后已排序的数组的子数组大小 4 & 4 & 4 & 3；
第三次遍历，对子数组为4的数组八八归并，进行2次归并，归并后已排序的数组的子数组大小分别为 8 & 7；
第四次遍历，对子数组为8的数组归并。进行1次归并，归并后已排序的数组的子数组大小 15，完成排序。
代码
public class MergeBU {
private static Comparable[] aux;
public static void sort(Comparable[] a)
{
int N = a.length;
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, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
private static void merge(Comparable[] a, int lo, int mid, int hi)
{
//见上原地归并的方法
}
}性能分析和特点
无论是【自顶向下】归并还是【自底向上】归并，其实都是一样的算法。这实际是分治思想中【递归】和【迭代】两种不同的解决方法。
运行时间依赖输入与否：【不依赖】
操作次数：需要1/2NlogN至NlogN次比较，最多需要6NlogN次数组访问（每次归并需要访问数组6N次，2N用来复制，2N用来归并移动回去，最多需要2N次比较）
影响运行时间的操作：【数组访问】
特点&使用范围：【辅助数组】所需【空间】和N的大小成正比。是【渐进最优】的基于比较的排序算法（归并排序在【最坏】情况下的比较次数和是NlogN，这也是所有【基于比较】的排序算法的最少比较次数）。性能分析上有【准确的上界】。
还可以进行的性能优化
- 因为小规模问题，递归调用过于频繁，影响性能。在处理小规模问题时使用其他方法，比使用递归算法要更优。比如对于长度小于15的子数组，使用插入排序可以缩短运行时间。
- 测试数组是否有序，在确定有序时跳过merge归并方法，处理有序数组的运行时间会变为线性。
- 可以在递归中，不将元素复制到辅助数组，虽然不能减少空间花费，但可以减少访问数组时间的花费。将数据从输入数组排序到辅助数组，并将数组从辅助数组中排序到输入数组。这需要在递归调用的每个层次交换数组和辅助数组的角色。
快速排序
快速排序利用分治思想将一个数组【分成】两个字数组两部分独立地排序。快速排序的关键是【切分】（partition）。
快速排序和归并排序是互补的。快速排序在排序前要切分数组，再继续递归排序；归并排序则是在递归调用后，再进行数组归并。
快速排序的切分
切分的方法是随机地取a[lo]作为【切分元素】，以它为基准，将小于它的放在其左边，大于它的放在其右边。
使用两个指针从数组两头分别向对面出发，在左边找到比【切分元素】大、右边找到比【切分元素】小的两个元素，【交换】两个的位置。在两个指针【相遇】时切分结束。
private static int partition(Comparable[] a, int lo, int hi)
{ // 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
int i = lo, j = hi + 1; // 左右扫描指针
Comparable v = a[lo]; // 切分元素
while (true)
{ // 扫描左右，检查扫描是否结束并交换元素
while (compare(a[++i], v) < 0) if (i == hi) break;
while (compare(v, a[--j]) < 0) if (j == lo) break;
if (i >= j) break;
exchange(a, i, j);
}
exchange(a, lo, j); // 将v = a[lo]放入正确的位置
return j; // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
}第一个扫描的是左边的【第二个】元素，【切分元素】一直在数组【第一位】。
为了将【切分元素】放在中间的正确位置，最后一次的交换将作为基准的【切分元素】 和指针越界指向的【小于切分元素】的元素互换位置。
随机打乱输入的快速排序
在切分不平衡时，如果第一次从最小元素切分，第二次从第二小的元素切分，如此这般每次只会移除一个元素。在这种情况下，快速排序的运行时间将会降低到【平方级】。在快速排序前随机打乱数组，可以避免这种糟糕的情况发生。
public class Quick {
private static Comparable[] aux;
public static void sort(Comparable[] a)
{
shuffle(a); // 消除对输入的依赖
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi); // 切分
sort(a, lo, j-1); // 将左半部分a[lo .. j-1]排序
sort(a, j+1, hi); // 将右半部分a[j+1 .. hi]排序
}
}三向切分的快排
三向切分处理大量重复元素的数组要更快。将数组切分成三部分，分别对应【小于】、【等于】和【大于】切分元素的数组元素。
巧妙的使用三个指针切分整个数组：
指针lt使得a[lo .. lt-1] 的元素小于v
指针i使得a[lt .. i-1] 的元素等于v
指针gt使得a[gt+1 .. hi] 的元素大于v
a[i] 小于v, 将 a[lt] 和 a[i] 交换，将 lt 和 i 加一；
a[i] 大于v, 将 a[gt] 和 a[i] 交换，将 gt 加一；
a[i] 等于v, 将 i加一；
public class Quick3way {
private static Comparable[] aux;
public static void sort(Comparable[] a)
{
shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
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, lo, lt-1);
sort(a, gt + 1, hi);
}性能分析和特点
快速排序是【最快】的【通用排序】算法。无数计算机系统中的实现也证明了这点，精心优化的快速排序也是很多编程语言的内置排序算法的实现。
运行时间依赖输入与否：依赖，糟糕的切分会让快速排序极为低效。极端情况下，最多需要N²/2次比较。
操作次数：平均需要2NlogN次比较，已经1/6的交换。极端情况下，最多需要N²/2次比较。
影响运行时间的操作：【比较】操作
特点&使用范围：快速排序的内循环指令很少，因为总是顺序访问数据，还能利用缓存。所以它的运行时间的增长数量级为cNlogN，c比其他的对数级别的排序算法的常数都要小。
但是快速排序也很脆弱，要设计时注意扫描指针越别界、保持输入随机性、切分内终止循环的条件、终止递归的条件才能保障快速排序的高效性。
堆排序
堆排序是基于二叉堆这一数据结构实现地一种排序算法。
二叉堆是一颗完全二叉树，父节点总是大于（小于）或等于子节点。因为堆的父节点的特性，将堆按递减顺序取出就可以得到排序结果。
堆操作
二叉堆重要的两个操作是【插入元素】或者【删除根节点】（根节点就是最大或者最小的元素，这取决于父节点和子节点保持何种关系）。
二叉堆可以在进行这两个操作改变了堆结构时，可以【恢复】堆的【顺序】。插入元素到数组末尾，使用上浮（swim）进行由下至上的堆有序化。从数组顶端删除根节点，并将最后元素放在顶端，使用下沉（sink）进行由上至下的堆有序化。
堆操作实现
堆通常使用数组实现，规定堆从1开始计数，符合二叉树结构，便于【取节点】操作。
代码使用面向【最大】元素的堆，这样排序后的数组是【从小到大】的，和前面的排序算法结果保持一致。
private static void sink(Comparable[] a, int k, int n) {
while (2*k <= n) // a[k]没有子节点时
{ //
int j = 2*k; // a[j]是a[k]第一个子节点
if (j < n && less(a, j, j+1)) j++; // a[j]与第二个子节点a[j+1]比较，取较大的那个
if (!less(a, k, j)) break; // a[k]大于或者等于它的最大子节点，则不需要继续下沉
exch(a, k, j); //a[k]小于它的最大子节点，交换位置
k = j;
}
}
private static boolean less(Comparable[] a, int i, int j) {
return a[i-1].compareTo(a[j-1]) < 0; // 堆的索引和数组相差1
}
private static void exch(Object[] a, int i, int j) {
Object swap = a[i-1]; a[i-1] = a[j-1]; a[j-1] = swap; // 堆的索引和数组相差1
}堆排序
for循环用于构造堆；while循环将数组【顶端】的最大元素和数组【最后】的元素交换位置，直到堆为空。
堆排序的主要工作是在第二阶段完成的。将堆中的最大元素删除，然后放进堆【缩小】后数组空出的位置。一直如此删除最大元素，就是交换最大元素和堆末尾元素再修复堆，就会将较大元素一直向数组后面移动。
public class Heap {
public static void sort(Comparable[] a)
{
int n = a.length;
// 每次确定一个父节点的左右子节点，确定所有父节点和子节点的关系时，堆就建好了
for (int k = n/2; k >= 1; k--) // 父节点的数量只占总结点数的一半不到，所以是k = n/2
sink(a, k, n);
int k = n;
while (k > 1) // 堆从1开始计数，循环k取到1为止
{
exch(a, 1, k--); // 交换根节点的最大元素和堆中最后的元素
sink(a, 1, k); // 下沉使新堆（k自减一，堆变小了）重新有序
}
}
}这个过程类似【选择排序】，但是需要的【比较】要少得多，堆提供了一种从未排序部分找到最大元素的有效方法。
性能分析和特点
运行时间依赖输入与否：【不依赖】
操作次数：少于2NlogN+2N次比较，少于NlogN+N次数的交换。（2N项来自于堆的构造，2NlogN项来自于每次下沉操作最大可能2NlogN次比较）
影响运行时间的操作：【比较】操作
特点&使用范围：堆排序是所知的唯一能够【同时】【最优】地利用【空间】和【时间】的方法，最坏情况下也能保证使用~2NlogN次比较和恒定的额外空间。也只需要几行代码就能实现较好的性能，但【不能】利用缓存，现代系统的应用中很少使用它。
文章评论