排序¶

选择排序¶

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 \(\sim \dfrac{N^2}{2}\) 次比较和 \(\sim N\) 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

public class Selection {
    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
        }
    }
}

冒泡排序¶

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

public class Bubble {
    public static <Key extends Comparable<Key>> void sort(Key[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int exchanges = 0;
            for (int j = n-1; j > i; j--) {
                if (less(a[j], a[j-1])) {
                    exch(a, j, j-1);
                    exchanges++;
                }
            }
            if (exchanges == 0) break;
        }
    }
}

插入排序¶

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。

平均情况下插入排序需要 \(\sim \dfrac{N^2}{4}\) 比较以及 \(\sim \dfrac{N^2}{4}\) 次交换；
最坏的情况下需要 \(\sim \dfrac{N^2}{2}\) 比较以及 \(\sim \dfrac{N^2}{2}\) 次交换，最坏的情况是数组是倒序的；
最好的情况下需要 \(N-1\) 次比较和 \(0\) 次交换，最好的情况就是数组已经有序了。

public class Insertion {
    public static void sort(Comparable[] 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=1，就可以使得整个数组是有序的。

public class Shell {
    public static void sort(Comparable[] a) {
        int n = a.length;

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ...
        int h = 1;
        while (h < n/3) h = 3*h + 1;

        while (h >= 1) {
            // h-sort the array
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            h /= 3;
        }
    }
}

归并排序¶

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法¶

归并方法将数组中两个已经排序的部分归并成一个。

// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
    assert isSorted(a, lo, mid);
    assert isSorted(a, mid+1, hi);

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    // merge back to a[]
    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++];
    }

    // postcondition: a[lo .. hi] is sorted
    assert isSorted(a, lo, hi);
}

自顶向下归并排序¶

将一个大数组分成两个小数组去求解。因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 \(O(N \log N)\)。

public class Up2DownMergeSort<T extends Comparable<T>> {
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int mid = l + (h - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, h);
        merge(nums, l, mid, h);
    }
}

自底向上归并排序¶

先归并那些微型数组，然后成对归并得到的微型数组。

public class Down2UpMergeSort<T extends Comparable<T>> {
    public void sort(T[] nums) {
        int N = nums.length;
        aux = (T[]) new Comparable[N];

        for (int sz = 1; sz < N; sz += sz) { //每一趟归并的数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}

快速排序¶

基本实现¶

通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

public class QuickSort<T extends Comparable<T>> {
    public void sort(T[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}

切分¶

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

private int partition(T[] nums, int l, int h) {
    int i = l, j = h + 1;
    T v = nums[l];
    while (true) {
        while (less(nums[++i], v) && i != h) ;
        while (less(v, nums[--j]) && j != l) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

性能分析¶

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下，复杂度为 \(O(N \log N)\)
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 \(\sim \dfrac{N^2}{2}\)。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组

算法改进¶

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分¶

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {
    protected void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int lt = l, i = l + 1, gt = h;
        T v = nums[l];
        while (i <= gt) {
            int cmp = nums[i].compareTo(v);
            if (cmp < 0) {
                swap(nums, lt++, i++);
            } else if (cmp > 0) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        sort(nums, l, lt - 1);
        sort(nums, gt + 1, h);
    }
}

基于切分的快速选择算法¶

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 \(k\) 个元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 \((N+\dfrac{N}{2}+\dfrac{N}{4}+\cdots)\)，直到找到第 \(k\) 个元素，这个和显然小于 \(2N\)。

public T select(T[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (h > l) {
        int j = partition(nums, l, h);

        if (j == k) {
            return nums[k];

        } else if (j > k) {
            h = j - 1;

        } else {
            l = j + 1;
        }
    }
    return nums[k];
}

堆排序¶

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

构建堆¶

无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。

交换堆顶元素与最后一个元素¶

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /**
     * 数组第 0 个位置不能有元素
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }

    private void sink(T[] nums, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1))
                j++;
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}

一个堆的高度为 \(\log N\)，因此在堆中插入元素和删除最大元素的复杂度都为 \(\log N\)。

对于堆排序，由于要对 \(N\) 个节点进行下沉操作，因此复杂度为 \(N \log N\)。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

比较¶

算法	稳定性	时间复杂度	空间复杂度	备注
选择排序	×	\(N^2\)	\(1\)
冒泡排序	√	\(N^2\)	\(1\)
插入排序	√	\(N \sim N^2\)	\(1\)	时间复杂度和初始顺序有关
希尔排序	×	\(N\) 的若干倍乘于递增序列的长度	\(1\)	改进版插入排序
快速排序	×	\(N \log N\)	\(\log N\)	递归使用 \(\log N\) 的空间
三向切分快速排序	×	\(N \sim N \log N\)	\(\log N\)	适用于有大量重复主键
归并排序	√	\(N \log N\)	\(N\)
堆排序	×	\(N \log N\)	\(1\)	无法利用局部性原理

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 \(\sim C \cdot N \log N\)，这里的 \(C\) 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

排序方法	平均时间	最好时间	最坏时间
桶排序 (不稳定)	\(O(n)\)	\(O(n)\)	\(O(n)\)
基数排序 (稳定)	\(O(n)\)	\(O(n)\)	\(O(n)\)
归并排序 (稳定)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)
快速排序 (不稳定)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n^2)\)
堆排序 (不稳定)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)
希尔排序 (不稳定)	\(O(n^{1.25})\)
冒泡排序 (稳定)	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)
选择排序 (不稳定)	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)
直接插入排序 (稳定)	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)