排序算法

分析排序算法

执行效率

对于排序算法执行效率的分析，一般会从这几个方面来衡量：

最好情况、最坏情况、平均情况时间复杂度：有序度不同的数据，对排序的执行时间有影响
时间复杂度的系数、常数、低阶：实际开发中，待排序的数据规模是 10/100/1000 这样的小规模，所以，在对同一阶时间复杂度的排序算法性能对比时，要把系数、常数、低阶也考虑进来
比较次数和交换（或移动）次数：基于比较的排序算法的执行过程，会涉及元素比较和元素交换/移动的操作。所以，在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去

内存消耗

算法的内存消耗通过空间复杂度来衡量，针对排序算法的空间复杂度，要引入了一个新的概念，原地排序（Sorted in place），原地排序算法，就是特指空间复杂度是 $O(1)$ 的排序算法。

稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性（如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变）。

排序算法是否稳定的影响，主要是在实际的软件开发中，使用对象的某个key来排序而非一个整数（key的先后顺序有实际的业务意义，而一个整数的先后顺序没有影响）。看下面具体的例子来感受一下。

现在要给电商交易系统中的“订单”排序。订单有两个属性：

下单时间
订单金额

排序的需求：

现在有 10 万条订单数据，按照金额从小到大对订单数据排序
对于金额相同的订单，按照下单时间从早到晚有序

最先想到的方法是：

先按照金额对订单数据进行排序
再遍历排序之后的订单数据，对于每个金额相同的小区间按照下单时间排序

这种排序思路理解起来不难，但是实现起来会很复杂。借助稳定排序算法，这个问题可以非常简洁地解决。

解决思路是这样的：

先按照下单时间（注意是按照下单时间，不是金额）给订单排序
排序完成之后，用稳定排序算法，按照订单金额重新排序

两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。

因为，稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

第一次排序之后，所有的订单按照下单时间从早到晚有序
在第二次排序中，使用稳定排序算法，经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序

常见排序算法

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

假设待排序数据为4,5,6,3,2,1，从小到大进行排序，第一次冒泡的详细过程如下图：

要完成所有数据的排序，需要进行6次冒泡操作：

将上述冒泡过程进行优化，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再执行冒泡操作，如下示例：

在冒泡的过程，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 $O(1)$ ，是原地排序算法。
在冒泡的过程中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，是稳定排序算法。
时间复杂度：
1. 最好情况，待排序数据有序（满有序度），只需要进行一次冒泡，时间复杂度是 $O(n)$
2. 最坏情况，待排序数据倒序（有序度为0），要进行n次冒泡，时间复杂度是 $O(n^2)$
3. 平均情况，根据数据初始的有序度假设为满有序度的一般即 $\frac{n*(n-1)}{4}$ ，时间复杂度是 $O(n^2)$

有序度

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示：a[i] <= a[j], 如果i < j 逆序度的定义正好跟有序度相反（默认从小到大为有序）：a[i] > a[j], 如果i < j

逆序度 = 满有序度 - 有序度。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

如{2,4,3,1,5,6}的有序度是11，{6,5,4,3,2,1}的有序度是0。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。

不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是 $\frac{n*(n-1)}{2}$ 减去初始有序度。

插入排序

使用动态排序向一个已经有序的数据集合中添加数据，插入后依然保持数据有序，即遍历数组，找到数据应该插入的位置将其插入即可。

对于一组静态数据（即数据集合的元素个数不变），借助上面的思想实现插入排序。

将数组中的数据分为两个区间，已排序区间和未排序区间
初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。

假设有待排序数据为4,5,6,3,2,1，左侧为已排序区间，右侧为未排序区间。

插入排序也包含两种操作：

元素的比较
元素的移动

当需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 $O(1)$ ，是原地排序算法
在插入排序中，对于值相同的元素，可以将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定排序算法
时间复杂度
1. 最好情况，待排序数据有序（满有序度），只需从尾到头遍历一遍有序数据，时间复杂度是 $O(n)$
2. 最坏情况，待排序数据倒序（有序度为0），则每次插入都相当于在数组的第一个位置插入新的数据，时间复杂度是 $O(n^2)$
3. 平均情况，（数组这种数据结构插入数据的平均时间复杂度是 $O(n)$ ）对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度是 $O(n^2)$

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序算法运行过程中不需要额外的空间，空间复杂度为 $O(1)$ ，是原地排序算法。
在选择排序中，对于值相同的元素，选择先出现的值为最小值，这样就可以保持原有的前后顺序不变，但是，最小值会和前面的数据交换位置，这会导致其他的相同值的位置改变，所以选择排序是不稳定排序算法
时间复杂度：
1. 最好情况，待排序数据有序（满有序度），每个数据都要与数据集合中剩下的数据进行比较，时间复杂度 $O(n)$
2. 最坏情况，待排序数据倒序（有序度为0），每个数据都要与数据集合中剩下的数据进行比较，时间复杂度 $O(n^2)$
3. 平均情况，对选择排序来说，没有最好最坏情况，所有数据都要进行比较，时间复杂度 $O(n^2)$

插入比冒泡更受欢迎

冒泡排序和插入排序的时间复杂度都是 $O(n^2)$ ，都是原地排序算法：

冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度
插入排序不管怎么优化，元素移动的次数是一个固定值，是原始数据的逆序度

从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。

    // 冒泡排序中数据的交换操作：
    if (a[j] > a[j+1]) { // 交换
        a[j], a[j+1] = a[j+1], a[j]
        flag = true;
    }

    // 插入排序中数据的移动操作：
    if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
    } else {
        break;
    }

把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。

冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3*K 单位时间。
插入排序，数据移动操作只需要 K 个单位时间。

// 测试数据集合 []int{4, 5, 1, 6, 2, 3, 4, 5, 1, 6, 2, 3, 4, 5, 1, 6, 2, 3}

// 冒泡排序，每秒调用6659475次
goos: linux
goarch: amd64
pkg: deal/sort
BenchmarkBubbleSort
BenchmarkBubbleSort-4     6659475        183 ns/op
PASS

// 插入排序，每秒调用11622802次
goos: linux
goarch: amd64
pkg: deal/sort
BenchmarkInsertionSort
BenchmarkInsertionSort-4    11622802         99.2 ns/op
PASS

实际结果相差两倍，所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 $O(n^2)$ ，但是如果希望把性能优化做到极致，那肯定首选插入排序，它的算法思路也有很大的优化空间，如希尔排序。

三者对比

特定算法依赖特定的数据结构，这三种算法都依赖数组实现。

算法

是否原地排序

是否稳定

最好

最坏

平均

冒泡

$O(n)$

$O(n^2)$

插入

$O(n)$

$O(n^2)$

选择

$O(n^2)$

冒泡排序、插入排序、选择排序这三种排序算法，它们的平均时间复杂度都是 $O(n^2)$ ，比较高，适合小规模数据的排序。下面是两种时间复杂度为 $O(nlogn)$ 的排序算法，归并排序和快速排序，都用到了分治的思想，适合大规模数据排序。

归并排序

归并排序的核心思想是：

先把数组从中间分成前后两部分
然后对前后两部分分别排序
再将排好序的两部分合并在一起，这样整个数组就都有序了

归并排序使用的就是分治思想，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

分治思想和递归思想很像，分治算法一般都是用递归来实现。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。

归并排序使用分治思想，用递归实现：

分析递推公式：MergeSort(p...r)=merge(mergeSort(p...q)+mergeSort(q+1...r)),q=(p+r/2)
找到终止条件：p>=r
将递推公式翻译成递归代码

在递推公式中，mergeSort()函数是被分解后的子问题，merge()函数是将已经有序的前后两部分合并为一个整体有序的数据集合，具体过程如下：

在函数内申请一个临时数组
分别从头开始比较已经有序的前后两部分
将较小的那一个先放入临时数组中
继续整个过程直到一个子数组中没有数据
将剩下的数组中全部数据直接插入临时数组末尾
将临时数组中的数据拷贝到原数组中

性能分析

归并排序稳不稳定关键要看 merge() 函数，即两个有序子数组合并成一个有序数组的那部分代码，可以保证值相同的元素，在合并前后的先后顺序不变，是稳定排序算法。
递归的是时间复杂度公式： $T(a)=T(b)+T(c)+K$ ，其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。所以归并排序的时间复杂度的计算公式是：
```
# n=1时，只需要常量级的执行时间，所以表示为C。
T(1) = C

# n>1
T(n) = 2*T(n/2) + n；

# 继续分解
T(n) = 2*T(n/2) + n
   = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
   = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
   = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
   ......
   = 2^k * T(n/2^k) + k * n
   ......

# 得到结果
T(n) = 2^k ×　T(n/2^k)　+　kn
# 当ｎ＝１时
T(n/2^k)=T(1)
n/2^k=1
k=log2n

# 将ｋ带入公式
T(n)=Cn+nlog2n
```
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 $O(nlogn)$ 。
不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
在merge()函数中，创建了一个临时数据（额外申请的临时内存空间）用于存储中间结果。因此，归并排序不是原地排序算法，空间复杂度是 $O(n)$ 。因为，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小。

快速排序

快速排序，简称快排，利用的也是分治思想，有点像归并排序，但是思路完全不一样。快排的思想是：

要排序数组中下标从 p 到 r 之间的一组数据，选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
经过这上述步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

分治的思想，可以用递归的方式来实现：

递推公式：QuickSort(p...r)=quickSort(p...q)+quickSort(q+1...r)
终止条件：p>=r
递推公式翻译为递归代码

    // 快速排序，A是数组，n表示数组的大小
    quick_sort(A, n) {
        quick_sort_c(A, 0, n-1)
    }
    // 快速排序递归函数，p,r为下标
    quick_sort_c(A, p, r) {
        if p >= r then return

        q = partition(A, p, r) // 获取分区点
        quick_sort_c(A, p, q-1)
        quick_sort_c(A, q+1, r)
    }

实现的关键就是分区函数partition()：随机选择一个元素作为 pivot（一般情况下，可以选择 p 到 r 区间的最后一个元素），然后对 $A[p…r]$ 分区，函数返回 pivot 的下标。

在不考虑空间复杂度的情况下，申请两个临时数组分别存放大于和小于pivot的数据，最后将两个数组的数据以此拷贝到原数组中。

快排是原地排序算法，即空间复杂度得是 $O(1)$ ，所以 partition() 分区函数就不能占用太多额外的内存空间，就需要在 $A[p…r]$ 的原地完成分区操作。

func partition(list []int, head int, tail int) int {
    pivot := list[tail]
    i := head
    for j := head; j < tail; j++ {
        if list[j] < pivot {
            list[i], list[j] = list[j], list[i]
            i++
        }
    }
    // 遍历一遍数组，说明i之前的都是小于pivot
    // 交换i与pivot的值
    list[i], list[tail] = list[tail], list[i]
    return i
}

这里的处理有点类似选择排序：

通过游标 i 把 $A[p…r-1]$ 分成两部分
$A[p…i-1]$ 的元素都是小于 pivot 的，称为“已处理区间”， $A[i…r-1]$ 是“未处理区间”
每次都从未处理的区间 $A[i…r-1]$ 中取一个元素 $A[j]$ ，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 $A[i]$ 的位置

数组的插入操作，需要搬移数据，非常耗时。有一种处理技巧，就是交换，在 $O(1)$ 的时间复杂度内完成插入操作。这里借助这个思想，只需要将 $A[i]$ 与 $A[j]$ 交换，就可以在 $O(1)$ 时间复杂度内将 $A[j]$ 放到下标为 i 的位置。

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，那么元素的位置可能发生改变，所以快速排序不是稳定的排序算法。

性能分析

时间复杂度
快排也是递归实现的，根据归并的分析思路，快排的时间复杂度也是 $O(nlogn)$ ：
```
T(1) = C；   // n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； // n>1
```
这里的前提条件是，pivot的选择很合适刚好可以将数组分成比较均匀的两部分，这是一种最好情况。
那么在最坏情况下，pivot不能将数组划分的较均匀，如原数组已经有序，需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 $\frac{n}{2}$ 个元素，这种情况下，快排的时间复杂度就从 $O(nlogn)$ 退化成了 $O(n^2)$ 。
空间复杂度： $O(1)$ ，不稳定的原地排序算法。

归并与快排对比

归并排序的处理过程是由下到上，先处理子问题，然后再合并。
快速排序的处理过程是由上到下，先分区，然后再处理子问题。
归并排序虽然是稳定的、时间复杂度很稳定为 $O(nlogn)$ 的排序算法，但它是非原地排序算法（合并函数无法在原地执行），所以应用没有快排广泛。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

算法

是否原地排序

是否稳定

最好

最坏

平均

归并

$O(nlogn)$

快排

$O(nlogn)$

$O(n^2)$

$O(nlogn)$

线性排序算法

时间复杂度都是线性的，因为是非基于比较的排序算法，不涉及元素之间的比较操作，但是对要排序的数据要求很苛刻，所以重点的是掌握这些排序算法的适用场景。

桶排序

桶排序核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

时间复杂度：

假设待排序的数据有 n 个，
把它们均匀地划分到 m 个桶内，每个桶里就有 $k=\frac{n}{m}$ 个元素。
每个桶内部使用快速排序，时间复杂度为 $O(k *logk)$ 。
m 个桶排序的时间复杂度就是 $O(m*k*logk)$ ，因为 $k=\frac{n}{m}$ ，所以整个桶排序的时间复杂度就是 $O(n*log(\frac{n}{m}))$ 。
当桶的个数 m 接近数据个数 n 时， $log(\frac{n}{m})$ 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 $O(n)$

桶排序对数据的要求非常苛刻：

待排序数据需要容易划分成 m 个桶，并且，桶与桶之间有天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
数据在各个桶之间的分布要比较均匀，否则桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 $O(nlogn)$ 的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

计数排序

计数排序是桶排序的一种特例。当要排序的 n 个数据，这n个数据的范围并不大，如最大值是 k，把数据划分成 k 个桶，那么每个桶内的数据的值都是相同的，只是每个桶内的数据量不同，这样省掉了桶内排序的时间，只需要遍历数据并放入对应的桶中。

例子

假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩放在一个数组 $A[8]$ 中，它们分别是：2，5，3，0，2，3，0，3。

考生的成绩从 0 到 5 分，使用大小为 6 的数组 $C[6]$ 表示桶，其中下标对应分数。 $C[6]$ 内存储的并不是考生，而是对应的考生个数，只需要遍历一遍考生分数，就可以得到 $C[6]$ 的值。

分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 $R[8]$ 中，会保存下标 4，5，6 的位置。

A[8]={2,5,3,0,2,3,0,3}
C[6]={2,0,2,3,0,1}
R[8]={0,0,2,2,3,3,3,5}

如何快速计算出，每个分数的考生在有序数组 $R[8]$ 中对应的存储位置呢？这个处理方法非常巧妙，很不容易想到。

思路是这样的：对 $C[6]$ 数组顺序求和， $C[6]$ 存储的数据就变成了下面这样子。 $C[k]$ 里存储小于等于分数 k 的考生个数。

C[6]={2,2,4,7,7,8}

数据准备完成后开始计数排序：

从后到前（算法稳定的根源）依次扫描数组 A，当扫描到 3 时，从数组 C 中取出下标为 3 的值 7
到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个
1. 也就是说， 3 是数组 R 中的第 7 个元素
2. 也就是说，数组 R 中下标为 6 的位置
把 3 放入到数组 R 中
此时小于等于 3 的元素就只剩下了 6 个了，所以相应的 $C[3]$ 要减 1，变成 6
以此类推，扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的

这种利用另外一个数组来计数的实现方式就很巧妙了。

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

如果数据精确到小数点后一位，需要将数据都乘以10转化为整数；如果数据是 $[-1000,1000]$ 需要将数据都加1000转化为整数。

基数排序

如何实现手机号码的排序，借助稳定排序算法，这里有一个巧妙的实现思路：

先按照最后一位来排序手机号码，
再按照倒数第二位重新排序，
以此类推，
最后按照第一位重新排序。
经过 11 次排序之后，手机号码就都有序了。

注意，这里按照每位来排序的排序算法要是稳定的，否则最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。

根据每一位来排序，可以用桶排序或者计数排序，它们的时间复杂度是 $O(n)$ 。

如果要排序的数据有 k 位，就需要 k 次桶排序或者计数排序，总的时间复杂度是 $O(k*n)$ 。当 k 不大的时候，基数排序的时间复杂度就近似于 $O(n)$ 。

对于非等长数据排序，如字典中的英文单词。可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，然后就可以使用基数排序。

基数排序要求待排序的数据是可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
每一位的数据范围不能太大，要可以用线性排序算法（桶排序、计数排序）来排序，否则，基数排序的时间复杂度就无法做到 $O(n)$ 了。

排序优化

选择合适的排序算法

算法

时间复杂度

稳定

原地

冒泡

$O(n^2)$

插入

$O(n^2)$

选择

$O(n^2)$

归并

$O(nlogn)$

快排

$O(nlogn)$

桶

$o(n+k)$ ，k是数据范围

计数

$o(n)$

基数

$o(dn)$ ，d是维度

线性排序算法的时间复杂度比较低，适用场景比较特殊
如果对小规模数据进行排序，选择时间复杂度是 $O(n^2)$ 的算法
如果对大规模数据进行排序，选择时间复杂度是 $O(nlogn)$ 的算法更加高效
归并排序空间复杂度是 $O(n)$ ，消耗的内存空间翻倍，应用不广泛
快速排序在最坏情况下的时间复杂度是 $O(n^2)$ ，需要优化一下，降低出现最坏情况的概率

优化快速排序

如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 $O(n^2)$ ，主要原因是分区点选的不够合理。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

如果很粗暴地直接选择第一个或者最后一个数据作为分区点，不考虑数据的特点，肯定会出现最坏情况，时间复杂度是 $O(n^2)$ 。

为了提高排序算法的性能，要尽可能地让每次分区都比较平均。下面是两种比较常见和简单的分区算法：

三数取中法：从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点（如果要排序的数组比较大，可用“五数取中”或者“十数取中”）
随机法：每次从要排序的区间中，随机选择一个元素作为分区点，从概率的角度来看，不大可能会出现每次分区点都选的很差的情况
更多其他的方法

快速排序使用递归实现，因此递归存在的问题，快排也需要注意警惕堆栈溢出：

限制递归深度
通过在堆上模拟手动实现函数调用栈手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制

实例

glibc中的qsort()函数：

qsort() 会优先使用归并排序来排序输入数据（数据量小，空间换时间，归并时间复杂度稳定）
要排序的数据量比较大的时候，qsort() 会改为用快速排序算法来排序（数据量大，时间换空间）
通过实现堆上栈来解决递归过深导致堆栈溢出的问题
在快排过程中，当待排序区间中，元素的个数<=4 时，qsort()退化为插入排序（小规模数据量， $O(n^2)$ 时间复杂度并不一定比 $O(nlogn)$ 执行时间长）

算法的性能可以通过时间复杂度来分析，但是，这种复杂度分析是比较偏理论的，实际上时间复杂度并不等于代码实际的运行时间。时间复杂度代表的是一个增长趋势。对于小数据量的排序，可以选择比较简单、不需要递归的插入排序算法。

假设 k=1000，c=200，当对小规模数据（比如 n=100）排序时， $n^2$ 的值实际上比 $knlogn+c$ 还要小。

knlogn+c = 1000 * 100 * log100 + 200 远大于10000

n^2 = 100*100 = 10000
// 对于小规模数据的排序，O(n^2) 的排序算法并不一定比 O(nlogn) 排序算法执行的时间长

最后更新于4年前

这有帮助吗？