初级排序算法
标准的排序算法应该有一个交换器exch()、一个比较器less()，并且需要有一个检验器isSorted()和一个打印器show()来验证数组是否完成排序。评价一个排序算法需要关注这个算法的运行时间和额外的内存使用情况。
// 比较器
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// 交换器
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
// 检验器
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;
}
// 打印器
private static void show(Comparable[] a) { // 在单行中打印数组
for (int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}
选择排序
首先，找到数组中最小的那个元素，其次，将它和数组的第 一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中 找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
算法性能：对于长度为 N 的数组，选择排序需要大约 $\frac{N^2}{2}$ 次比较和 N 次交换。
特点：
- 运行时间和输入无关
- 数据移动最少（交换次数与数组大小是线性关系）
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++)
if (less(a[j], a[min])) min = j;
exch(a, i, min);
}
}
插入排序
特点：
- 交换操作和数组中倒置的数量相同
- 需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一
public static void sort(Comparable[] a) { // 将a[]按升序排列
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}
}
改进： 将内循环中较大的元素都向右移动以减少访问数组的次数
希尔排序
使数组中任意间隔为h的元素是有序的，一开始将h设置的很大（便于将小元素移到很远的地方），然后逐渐减小间隔h，最终h为1，数组完全有序。
希尔排序可以用于大型数组（数组越大相对于插入排序性能越好），对非随机数组表现也很好。
该排序算法是对插入排序的优化，但是其性能很难严格描述（时间复杂度可以近似认为是O(NlgN)）。
public static void sort(Comparable[] a)
{ // 将a[]按升序排列
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
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 && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h/3;
}
}
归并排序
- 所谓归并就是先将一个整体分成多个模块，依次完成每个模块的任务目标，再将这些不同模块合并到一个整体中。
- 实现归并排序的一种方法就是将两个不同的有序数组归并到第三个数组。
- 归并排序的算法核心在于归并而非排序
- 归并排序
归并策略：原地归并
特点： 能在数组中移动元素而不需要额外的空间
前、后半部分分别已排序，对两部分进行合并：
public 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++];
else if (j > hi ) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
自顶向下的归并排序
利用上述归并方法，我们可以做出一个递归的算法，不断地将带排序数组分割成多个部分直到数组大小为1，再逐层归并回原来的数组，完成排序。
对于长度为N的任意数组，自顶向下的归并排序需要 $\frac{1}{2}N\lg{N}$ 至 $N\lg{N}$ 次比较，最多需要访问数组$6N\lg{N}$次（每次归并最多需要访问数组6N次，其中2N次用来复制，2N次用来将排好序的元素移动回去，另外最多比较2N次）。
public class Merge {
private static Comparable[] temp;
public static void sort(Comparable[] a) {
temp = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 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) {
int i = lo;
int j = mid + 1;
for (int k = lo; k <= hi; k++) {
temp[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i >= j) a[k] = temp[j++];
else if (j >= hi) a[k] = temp[i++];
else if (less(a[i], a[j])) a[k] = a[i++];
else a[k] = a[j++];
}
}
}
自底向上的归并排序
该算法采用分治的思想，先将一个大问题分解成若干个小问题分别解决，然后用所有小问题的答案来解决整个大问题。
该算法与自顶上下的归并排序算法的时间复杂度相同。
private static Comparable[] temp;
public static void sort(Comparable[] a) {
int N = a.length;
temp = new Comparable[N];
for (int sz = 0; sz < N; sz += sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz)
merge(a, lo, lo + sz, Math.min(lo + sz + sz - 1, N - 1));
}
}
快速排序
快速排序也用到了分治的思想，也就是将一个数组分成两个子数组再分别独立地排序。
特点：
- 与归并排序不同，归并排序需要将两个排序好的子数组再合并成一个新数组，而快速排序在将两个子数组分别排好序后整个数组就自然有序了；
- 快速排序的递归调用在处理整个数组之后；
- 快速排序中，切分的位置取决于数组的内容；
- 快速排序的关键在于切分（partition）
将长度为 N 的无重复数组排序，快速排序平均需要 $2N\ln{N}$ 次比较（以及 1/6 的交换）。
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (lo <= hi) return;
int mid = partition(a, lo, hi);
sort(a, lo, mid - 1);
sort(a, mid + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo + 1;
int j = hi;
Comparable b = a[lo];
while (true) {
while (less(i++, b)) if (i > hi) break;
while (less(b, j++)) if (j <= lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
s}
改进快速排序
小数组切换到插入排序
考虑到递归，快速排序的sort()方法在小数组中也会调用自己，因此对于小数组，快速排序比插入排序慢。我们希望在排序小数组时应该切换到插入排序，改动如下：
将sort()中源代码
if (hi <= lo) return;
改成：
if (hi <= lo + 10) {
Insertion.sort(a, lo, hi);
return;
}
三取样切分
使用子数组的一小部分元素的中位数而非随机选取一个数来切分数组。
一般将取样大小设为3并用大小居中的元素切分的效果最好，修改partition代码如下：
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo + 1;
int j = hi;
Insertion.sort(a, lo, lo + 2);
exch(a, lo, lo + 1);
Comparable b = a[lo];
while (true) {
while (less(a[i++], b)) if (i > hi) break;
while (less(b, a[j--])) if (j <= lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
熵最优排序
对于有大量重复元素的数组，可以通过将数组切分为大于、等于、小于切分元素的三部分，其中等于切分元素的部分就不需要再进行切分了。
实现该策略的一种解法是三向切分的快速排序：创建两个指针，使这两个指针指向的两个方向分别小于、大于切分元素
private static int[] partition(Comparable[] a, int lo, int hi) {
int i = lo + 1;
int lt = lo + 1;
int gt = hi;
Comparable b = a[lo];
while(true) {
if (lt <= gt || i > hi) break;
else if (less(b, a[i])) exch(a, i++, lt++);
else if (less(a[i], b)) exch(a, i++, gt--);
else i++;
}
return new int[] {lt, gt};
}