时间复杂度 O(lgn) 的通用算法

Divide and Conquer

quick sort
merge sort

这两者的思想很像：前者是选取一个 pivot，把数组分为两部分，再分治两部分即可。因为选取的 pivot 可能不能很好等分数组，最差的情况下时间复杂度是 O(n^2)；后者是将数组等分为两部分，分别排序后再 merge，数组的话 merge 的时候还要 O(n) 的空间保存 merge 的新数组。

树

binary tree sort: 构造一棵二叉搜索树，然后中序遍历得到的就是排序好的数组
heap sort: 构造最小（大）堆，构造好后，不断取出堆顶元素即可

特定情景下时间复杂度 O(n) 的算法

Counting sort^[1]

适合待排序数分布在一个小区间内。当待排序数是 n 个 0 到 k 之间的整数时，它的时间复杂度是 Θ(n+k)。维基百科上的那个解法需要 O(n+k)，下面这种写法可以 in place。

public void countSort(int[] nums, int k) {
    int[] counts = new int[k+1];
    for (int i = 0; i < nums.length; i++) {
        counts[nums[i]]++;
    }
    int i = 0, j = 0;
    while (i < counts.length) {
        if (counts[i] == 0) {
            i++;
            continue;
        }
        nums[j++] = i;
        counts[i]--;
    }
}

Bucket sort

假设 n 个数分布在 [A, B] 内，把这个区间等分成 k 个桶，则每个数都落在某个桶内。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后从不是空的桶子里把数再放回原来的序列中。这种算法适合数在区间上均匀分布的情形，这样每个桶内的元素就是 n / k 个，对桶内元素排序时间是 O(1)，整个桶排序时间复杂度 O(n+k)。