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) 可能会更快。

Last updated