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

小灰灰 2024-03-30 15:36 59阅读 0赞

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

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

--------------------

#### 文章目录 ####

*  常用排序算法的时间复杂度一览
 *  非线性排序
 *   *  1 选择排序
     *  2 插入排序
     *  3 冒泡排序
     *  4 希尔排序
     *  5 快速排序
     *  6 堆排序
     *  7 归并排序
 *  线性排序
 *   *  8 桶排序
     *  9 计数排序
     *  10 基数排序
 *  总结

--------------------

## 非线性排序 ##

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

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

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

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

**为什么要考察稳定性？**

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

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

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

### 1 选择排序 ###

![在这里插入图片描述][278a162f34a7487eb6f368cfd4b84524.gif_pic_center]

### 2 插入排序 ###

![在这里插入图片描述][7607b42b2c4e4390a2d5e8a151d813b0.gif_pic_center]

### 3 冒泡排序 ###

![在这里插入图片描述][d826e0685a284d66990000c72e7b8f20.gif_pic_center]

### 4 希尔排序 ###

![在这里插入图片描述][1c48156535674d649a585b8bcde29cd7.png_pic_center]

### 5 快速排序 ###

以下为第一趟排序，基值为30，让小于30的所有数据在30左边，大于30的数据在30的右边，然后递归分别对30左边和右边的数组进行相同的操作。  
![在这里插入图片描述][4710526273824c1fabb7d8d219db0146.jpeg_pic_center]

### 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 归并排序 ###

要理解和学会归并的思想  
![在这里插入图片描述][eac4659da02c46daaae948508562e848.gif_pic_center]

## 线性排序 ##

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

### 8 桶排序 ###

核心思想是：将将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。举个简单的例子：  
![在这里插入图片描述][11368cbf92984df48f0f67a1523848bd.png_pic_center]  
每个桶内进行快速排序后，根据桶的编号汇总数据即可。  
**使用要求：**

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”不会影响到原有的大小顺序。这样就可以继续用基数排序了。

--------------------

## 总结 ##

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

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

[278a162f34a7487eb6f368cfd4b84524.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8e82577f8ec04599a0e62cc6802ee253.gif
[7607b42b2c4e4390a2d5e8a151d813b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8311ecb3c6cd4075adab1ab1bb608d61.gif
[d826e0685a284d66990000c72e7b8f20.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9ebfa71e1de74e13b1e5e0d5261398e1.gif
[1c48156535674d649a585b8bcde29cd7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/200c4c910e4348efb13567bb28389a26.png
[4710526273824c1fabb7d8d219db0146.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/95e23ef0f18a4e7394a482599b0c6f1a.jpeg
[eac4659da02c46daaae948508562e848.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/18ea047c81834c76aaffeff125f27d60.gif
[11368cbf92984df48f0f67a1523848bd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/84e77280db6c48f483852e894a0b0d2f.png
[Link 1]: https://blog.csdn.net/qq_35556064/article/details/82888717?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167305773816800211597504%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167305773816800211597504&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-82888717-null-null.142%5Ev70%5Ewechat,201%5Ev4%5Eadd_ask&utm_term=%E5%90%84%E7%B1%BB%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E5%A4%8D%E6%9D%82%E5%BA%A6&spm=1018.2226.3001.4187