常用排序算法的时间复杂度一览

一文看懂各类排序的时间复杂度
总是记不住各类算法的时间复杂度，今天就一起来看看吧！

---

---

非线性排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
选择排序	O(N^2)	O(N^2)	O(N^2)	不稳定	O(1)
插入排序	O(N)	O(N^2)	O(N^2)	稳定	O(1)
冒泡排序	O(N)	O(N^2)	O(N^2)	稳定	O(1)
希尔排序	O(N)	O(N^(3/2))	O(N^S)（1<S<2）	不稳定	O(1)
快速排序	O(NlogN)	O(NlogN)	O(N^2) （1<S<2）	不稳定	O(logN)
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	不稳定	O(1)
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	稳定	O(N)

注：logN表示以2为底N的对数。
稳定性：

待排序数据中有相同的数，排序之后相同的数与排序前的前后位置关系不变，则成为稳定排序算法。比如我们有一组数据2，9，3，4，8，3；按照大小排序之后就是2，3，3，4，8，9；两个3的前后顺序在排序前后保持不变，即稳定。

为什么要考察稳定性？

答：实际的开发任务中，并不是单纯的对数字进行排序，而是对象，需要根据对象的某个key进行排序。举个例子：现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有10万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。

最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。为什么呢？

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

1 选择排序

2 插入排序

3 冒泡排序

4 希尔排序

5 快速排序

以下为第一趟排序，基值为30，让小于30的所有数据在30左边，大于30的数据在30的右边，然后递归分别对30左边和右边的数组进行相同的操作。

6 堆排序

通常用于求top K问题
给大家看一道例题吧！

返回数组第k个最大数据

import java.util.PriorityQueue;

public class HeapTopK {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
        System.out.println(findK(arr, k));
    }

    /**
     * PriorityQueue 优先队列思想
     * 返回数组第k个最大数据
     *
     * @param nums
     * @param k
     */
    public static int findK(int[] nums, int k) {   //时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)，空间复杂度：O(K)
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        // k 堆的初始容量，(a,b) -> a -b 比较器
        PriorityQueue<Integer> minTop = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minTop.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            Integer topEle = minTop.peek();  // 返回队头元素（不删除），失败时前者抛出null
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minTop.poll();  // 获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
                minTop.offer(nums[i]);  // 在队尾插入元素，插入失败时抛出false，并调整堆结构
            }
        }
        return minTop.peek();
    }

}

7 归并排序

要理解和学会归并的思想

线性排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，时间复杂度都可以趋近于O(N)，因此称为线性时间非比较类排序。 只适用于一些特定的场合。

8 桶排序

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

每个桶内进行快速排序后，根据桶的编号汇总数据即可。
使用要求：

1. 需要能很方便的将数据划分成m个桶
2. 桶之间无需排序
3. 数据要尽量分布均匀

使用场景：适合于外部排序。

所谓外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。MySQL在排序的时候如果内存不够，就会使用外部排序，把数据分成多份，每份单独排序后写入临时文件，最后把这些有序的文件合成一个大文件。其通常采用的是归并排序算法。
比如说我们有10GB的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加载到内存中。这种情况就可以使用桶排序：

1. 先扫描文件找出金额的最小值和最大值。假设这里为1元和10万元。
2. 可以分100个桶，第1个桶放1-1000元的数据；第2个桶放1001-2000元的数据；…以此类推。每个桶是一个文件，并给文件按顺序编号。
3. 如果数据分布均匀，那每个文件大约100M，可以依次加载到内存使用快排。如果数据分步不均匀，那可能需要对数据量大的桶继续进行桶排序，直到内存能装下。

9 计数排序

可以认为是桶排序的特殊情况：要排序的数据的范围不大的情况，假设范围是0到k，那么计数排序就是直接分配k+1个桶，每个桶内的数值都是相等的，省掉了桶内排序的过程。
举个例子：假设某省50万考生，需要根据成绩排序。成绩的范围是0-750，那么就可以申请一个长度为751的数组，下标对应分数0到750。遍历这50万的数据，对应分数上统计数量。最后只需要依次遍历这个数组：假设下标为0（即分数为0）的统计有100个，那么直接输出100个0；下标为1的有3个，那么再往后追加输出3个1；……直到下标为750，即可完成排序。因为只涉及扫描遍历操作，所以时间复杂度是O(n)。
使用场景：只能用于数据范围不大的情况，且数据都是正整数的情况（如果不是，需要先进行处理）。
备注：最终完成排序的数组，也可以使用前缀和的方式来实现，这个方法有点绕，有兴趣的可以自己百度了解下。

10 基数排序

原理是将整数按位数切割成不同的数字，然后按每个位数分别归类。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

举个例子：给10万个手机号码从小到大排序。
借助于稳定排序算法，从后往前，对手机号码的每一位进行稳定排序，如可以使用桶排序或者计数排序，即先对所有手机号的第10位进行桶排序，再对第0位……直到第0位。每次桶排序的时间复杂度为O(N)，假设要进行k次排序，则基数排序的时间复杂度为o(kN)。由于手机号通常是11位，所以这里时间复杂度为O(11N)，近似O(N)。
此外，如果待排序的字符串的长度不一致，可以先补"0"，因为根据ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。

---

总结

各个算法的时间复杂度都有些许差异，多看多回顾！

转载博客：常见排序算法的时间复杂度汇总