Sort

Preface

算法	是否原地	是否稳定	平均	最好	最坏	基于比较
冒泡	是	是	O(n^2)	O(n)	O(n^2)	是
插入	是	是	O(n^2)	O(n)	O(n^2)	是
选择	是	否	O(n^2)	O(n^2)	O(n^2)	是
归并	否: O(n)	是	O(nlogn)	O(nlogn)	O(nlogn)	是
快速	是	否	O(nlogn)	O(nlogn)	O(n^2)	是
堆	是	否	O(nlogn)	O(nlogn)	O(nlogn)	是
计数	否	是		O(n+k), k数据范围		否
桶	否	是		O(n)		否
基数	否	是		O(dn), d位数		否

评价排序算法的维度：

1. 时间复杂度：最好、最坏、平均，以及对应的原始数据类型。

2. 时间复杂度的系数、常数、低阶，时间复杂度反应的是随数据规模 n 增大的增长趋势，一般是在 n 很大的情况下得出。但是在实际中，n 可能不是很大，所以在同一个阶时间复杂度下，需要考虑系数、常数、低阶。

3. 比较次数与交换（移动）次数的分析。

4. 内存消耗。原地排序（sorted in place）指空间复杂度为 O(1) 的排序算法。

5. 稳定性，如果待排序的序列中存在值相等的元素，经过排序之后，相等的元素之间原有的先后顺序不变。实际中，我们是根据对象的某个 field 来排序，对象还有其它 field，所以需要分析稳定性。例子：订单有时间和金额，希望 order by amount, time，那么先对时间排序，然后用稳定的排序算法对金额排序，得到的结果就是金额从小到大，相同金额从早到晚。

Bubble Sort

描述：冒泡排序仅会操作相邻的两个元素，比较两个相邻元素，若不满足大小关系，则交换。每次冒泡会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。

优化：当某次冒泡没有数据交换时，则完成排序。

public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        boolean exchanged = false;
        for (int j = 1; j < n - i; j++) {
            if (nums[j - 1] > nums[j]) {
                exchanged = true;
                exchange(nums, j - 1, j);
            }
        }
        if (!exchanged) {
            break;
        }
    }
}
private void exchange(Integer[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

原地排序：只需要常量级的额外空间。

稳定排序：当相邻两个元素相等时，不交换就行。

最好时间复杂度：若数据本来有序，则只需要一次冒泡，所以最好为 O(n)。

最坏时间复杂度：若数据刚好为逆序，则要进行 n 次冒泡，所以最坏为 O(n^2)。

平均时间复杂度：

有序度是数组中具有有序关系的元素对的个数，有序元素对定义：a[i] <= a[j], i < j。如2, 4, 3, 1, 5, 6有序度为4 + 2 + 2 + 2 + 1 = 11。完全有序的数组的有序度叫满有序度(n * (n - 1) / 2)。逆序度 = 满有序度 - 有序度。

冒泡有两个比较和交换两个操作，每次交换，有序度加1，所以交换次数 = 逆序度。平均交换次数n * (n - 1) / 4，比较次数 > 交换次数，时间复杂度上限 O(n^2)，所以平均时间复杂度 O(n^2)。

注意此种平均时间复杂度分析并不严格。

Insertion Sort

描述：将数组分为两个区域，已排序和未排序，初始已排序为第一个元素。每次取未排序的第一个元素，在已排序中找到合适位置插入。

public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int tmp = nums[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (tmp < nums[j]) {
                nums[j + 1] = nums[j];
            } else {
                break;
            }
        }
        nums[j + 1] = tmp;
    }
}

特点：包含比较和移动两种操作。移动次数等于逆序度。

原地排序：不需要额外存储空间。

稳定排序：当两个元素相等时，将后面插入的元素放到前面出现的元素后面，就可以保证顺序不变。

最好时间复杂度：如数据本来有序，则不需要搬动任何数据，查找插入位置时从尾到头，则每次只需要比较一次，所以最好为 O(n)。

最坏时间复杂度：如果数据是倒序的，每次都要移动有序区域的所有数据，所以最坏为 O(n^2)。

平均时间复杂度：在有序数组中插入一个数据的平均时间复杂度为 O(n)，所以插入排序的平均时间复杂度为 O(n^2)。

为什么插入排序比冒泡排序更好？冒泡和插入的交换或移动次数是固定的，等于逆序度。但是冒泡一次交换需要三个操作，差插入一次移动仅需一个操作。

插入排序优化：希尔排序，开始用大的步长，最后一次就是普通的插入，但是基本已经排好序。用大的步长是每次可以移动较大的位置。

Selection Sort

描述：将数组分为两个区域，已排序和未排序，初始已排序为空，每次找到未排序的最小元素，放入已排序的末尾，即与未排序的第一个元素交换。

public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int min = nums[i];
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < min) {
                min = nums[j];
                minIndex = j;
            }
        }
        int tmp = nums[i];
        nums[i] = min;
        nums[minIndex] = tmp;
    }
}

原地排序：不需要额外存储空间。

最好、最坏、平均时间复杂度：都是 O(n^2)。

不稳定排序：每次都从未排序区域中找到最小，与未排序区域的第一个元素交换，破坏了稳定性。

冒泡排序与选择排序仅用作理论，实际中基本不用，而插入排序有时会用到。

若是链表实现，冒泡排序的交换操作更加复杂；插入排序不需要移动，直接插入；选择排序的交换同样比较复杂。

Merge Sort

描述：采用分治的思想。先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并。

public void sort(Integer[] nums) {
    mergeSort(nums, 0, nums.length - 1);
}

private void mergeSort(Integer[] nums, int p, int r) {
    if (p >= r) {
        return;
    }
    
    int q = (p + r) / 2;
    mergeSort(nums, p, q);
    mergeSort(nums, q + 1, r);
    merge(nums, p, r);
}

private void merge(Integer[] nums, int p, int r) {
    int q = (p + r) / 2;
    
    int[] tmp = new int[r - p + 1];
    
    int i = p, j = q + 1, cur = 0;
    while (i <= q && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[cur++] = nums[i++];
        } else {
            tmp[cur++] = nums[j++];
        }
    }
    
    for (; i <= q; i++) {
        tmp[cur++] = nums[i];
    }
    
    for (; j <= r; j++) {
        tmp[cur++] = nums[j];
    }
    
    cur = 0;
    for (int k = p; k <= r; k++) {
        nums[k] = tmp[cur++];
    }
}

递推公式：merge_sort(p, r) = merge(merge_sort(p, q), merge_sort(q + 1, r))

终止条件：p >= r；其中，q = (p + r) / 2。

稳定排序：关键看 merge 操作，在 merge 过程中，把 A[p, q] 中的元素先放入临时数组，那么值相同的元素保证了顺序不变，所以归并排序是稳定的。

最好、最坏、平均时间复杂度：都是 O(nlogn)，分析过程如下：

// 假设对 n 个元素进行归并排序时间为 T(n)，那么两个子数组进行归并排序的时间都是 T(n/2)，
// merge 操作的时间复杂度是 O(n)，所以递推公式如下
T(1)=C
T(n)=2*T(n/2)+K

其中 K 为将两个子问题合并所需时间，K = O(n)。所以归并时间复杂度为 O(nlogn)，与原始数据有序程度无关。

非原地排序：合并操作需要一个临时数组，最大为 n，所以归并排序的空间复杂度为 O(n)。

Quick Sort

描述：快排也是分治思想，将 A[p, r] 排序，选择 p 到 r 之间任意一个数据作为 pivot（分区点），将小于pivot 的放到左边，大于 pivot 的放到右边，pivot 放到中间。

public void sort(Integer[] nums) {
    _sort(nums, 0, nums.length - 1);
}

private void _sort(Integer[] nums, int p, int q) {
    if (p >= q) {
        return;
    }
    
    int r = partition(nums, p, q);
    _sort(nums, p, r - 1);
    _sort(nums, r + 1, q);
}

// 快排的分区函数类似选择排序：将数组分为两个区域，初始已处理为空，
// 每次从未处理选一个与 pivot 比较，若小于pivot，则放入已处理末尾，即与未处理的第一个元素交换。
private int partition(Integer[] nums, int p, int q) {
    int i = p;
    int pivot = nums[q];
    for (int j = p; j < q; j++) {
        if (nums[j] < pivot) {
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i++] = tmp;
        }
    }
    nums[q] = nums[i];
    nums[i] = pivot;
    return i;
}

递推公式：quick_sort(p, r) = quick_sort(p, q - 1) + quick_sort(q + 1, r)

终止条件：p >= r

不稳定排序：快速排序涉及交换，所以不稳定。

原地排序：分区函数不需要额外空间。

时间复杂度分析：大部分情况是 O(nlogn)，O(n^2) 的概率非常小，可以合理选择 pivot 来降低概率。最坏情况即数组已经有序，选择最后一个元素作为 pivot，则时间复杂度为 O(n^2)。.

T(1) = C
T(n) = 2 * T(n / 2) + n

归并排序与快速排序的区别：归并是由下到上，先处理子问题，再合并；快速是由上到下，先分区，再处理子问题。

求无序数组中第 K 大元素

思路：将数组 A[0:n-1] 最后一个元素 A[n-1] 作为 pivot，原地分区，分成了 A[0: p - 1], A[p], A[p + 1: n - 1]，若 p + 1 = K，则 A[p] 就是要求解的，否则按上述思路继续查找。

时间复杂度：n + n / 2 + n / 4 + n / 8 + ... + 1 = 2n - 1，为 O(n)。

线性排序

线性排序时间复杂度是线性 O(n) 的：桶排序、计数排序、基数排序。能做到线性，原因都是非基于比较，不涉及元素之间比较操作。

线性排序对数据的要求很严苛，都有各自的适用场景。

Bucket Sort

描述：将排序的数据分到几个有序的桶中，每个桶内单独排序，再按照桶的顺序依次取出。

时间复杂度：O(n)。n 个数据，m 个桶，每个桶的数据个数为 k = n / m，O(m*k*logk) = O(n*log(n/m))，当 m 接近 n 时，log(n/m) 很小。

对数据要求：1. 数据很容易划分成 m 个桶；2. 桶与桶有天然有序；3. 能够比较均匀分布在各个桶中。

适用场景：适合外部排序，数据量大，无法全部加载到内存中。

案例：10GB 的订单数据，只有几百 MB 内存，希望按照订单金额排序。1. 扫描一遍文件，得到订单金额所处范围；2. 根据范围分为 100 个桶，每个桶对应一个文件；3. 再扫描一遍，把数据分到 100 个文件中，若分布均匀，每个文件大约 100MB；4. 100 个文件分别放在内存中排序；5. 然后将 100 个文件依次写入到一个文件中；6. 若分布不均匀，则可以对数据比较多的小文件再次分割。

Counting Sort

描述：需要排序的 n 个数据，仅有 k 个可能值，则可以把数据划分到 k 个桶中，每个桶内的数据值一样，桶内不需要排序。

有人认为，计数排序是特殊的桶排序。我认为不是。因为桶排序中，每个桶存放的是所有数据，每个桶单独排序；而计数排序中，每个桶中存放的是数据的个数，算法思路不一样。

流程：假设数据 A[n] 有 k 个可能值。1. 先准备一个大小为 k 的数组 C，C 的下标为数据值，C 的值为数据值的个数；2. 扫描一遍数据，得到 C；3. 对 C 顺序求和，此时 C[i] 中存放的是小于等于 i 的个数；4. 准备数组 R[n]，从后往前扫描 A[n]，若值为 i，则R[C[i]]=i, C[i]=C[i]-1。

适用场景：数据值范围不大；只能给非负整数排序，若是其它类型，在不改变相对大小的情况下，转化为非负整数。

案例：考生满分 900 分，对高考成绩排序，则可以划分成 901 个桶。

Radix Sort

描述：比如，对手机号排序，从低位开始，每一位分别用线性排序。要求稳定的排序。

若数据不是等长，可以补齐。

适用场景：数据可以分割出位，位有递进关系，高位比较大，则低位就不用比较了，每一位的数据范围不大，对每位就可以用线性排序了。

工程应用

如何实现一个通用的、高性能的排序函数：

• 通用，所以不能选择对数据要求比较严格的线性排序。

• 小规模数据可选择 O(n^2)，大规模一般选择 O(nlogn)。

• O(nlogn) 比较多，Java 采用堆排序，C 采用快速排序。

• 归并用的少，原因是非原地。

• 解决快排在最坏情况 O(n^2) 的方式：a、首、尾、中三个数取中间值；b、随机；

• 快排递归，防止栈溢出，可以限制深度，也可以手动实现栈。

Glibc 的 qsort：

• 优先使用归并，在数据量小时。

• 数据量大，变成快排。

• 快排采用三数取中法。

• 自己在堆上实现栈。

• 当排序取件小于等于 4 时，退化为插入排序。

O(n^2) 算法不一定比 O(nlogn) 执行时间长：

• 时间复杂度反映的是增长趋势

• 但是会省略低阶、常数、系数，所以数据量小时，O(n^2) 可能会更快。