各种排序算法复杂度比较

客官°小女子只卖身不卖艺 2022-05-15 10:46 289阅读 0赞

#### 写在前面 ####

> 笔试题目当中会出现各种排序算法的比较，分为最好，最坏，平均情况的复杂度比较，在这里总结一下。

#### 主要内容 ####

![这里写图片描述][6524741_1489243629314_792B9001DFB7D6F2C5286D786EDED619]

> 最好情况

一般会这么问：在各自最优条件下以下算法复杂度最低的是

看清题目的要求是问在最优的条件下，所以插入排序和冒泡排序是最优的为o(n)的复杂度。

> 冒泡排序这里为啥最好情况时o(n)？  
> 冒泡排序的最坏和平均都是o(n\*n)，但是当原本的序列本身就是有序的时候，事实上可以添加一个标志位就可以搞定这个问题：此时只需要一次遍历就能知道结果。

public void bubbleSort(int arr[]) {
        boolean didSwap;
        for(int i = 0, len = arr.length; i < len - 1; i++) {
            didSwap = false;
            for(int j = 0; j < len - i - 1; j++) {
                if(arr[j + 1] < arr[j]) {
                    swap(arr, j, j + 1);
                    didSwap = true;
                }
            }
            if(didSwap == false)
                return;
        }    
    }

> 快排最好的情况是，每次正好中分，复杂度为O(nlogn)。最差情况，复杂度为O(n^2)，退化成冒泡排序

#### 快速排序的优化 ####

*  方法一：固定基准元（基本的快速排序）
 *  方法二：随机基准元
 *  方法三：三数取中
 *  方法四. 两种优化的方法：优化一：当待排序序列的长度分割到一定大小后，使用插入排序。优化二：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。
    
    [三种快速排序算法以及快速排序的优化][Link 1]

STLsort的快排优化：

STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。[STL sort 函数实现详解][STL sort]

基本快排时间复杂度证明：  
[快速排序时间复杂度数学证明][Link 2]

算法复杂度一样只是说明随着数据量的增加，算法时间代价增长的趋势相同，并不是执行的时间就一样，**这里面有很多常量参数的差别**，即使是同样的算法，不同的人写的代码，不同的应用场景下执行时间也可能差别很大。  
快排的最坏时间虽然复杂度高，但是在统计意义上，这种数据出现的**概率极小**，而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间，但是常量时间差很多。

> 堆排序和快排比较

堆排序的最坏时间复杂度是O(nlogn)，平均时间复杂度是O(nlogn)。但是堆排序的时间常数比较大，**因此从平均来看堆排序的时间复杂度反而是最差的**。 同级别下时间常数最大。

一般情况下，**快速排序效率要高于堆排序**。因为堆排序的常数较大（不过也是1～2之间吧）。  
快速排序的平均时间复杂度是O(1.39nlogn)。**一般来说，除非有需要绝对保证不能出现O(n^2)的要求，不使用堆排**。  
堆排序需要有效的随机存取。  
这是算法硬伤，没办法的。因为每次取一个最大值和堆底部的数据（记为X）交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来。从上面看出，**堆排序做了许多无用功**。

> 插入排序为什么在小数据上好于快速排序

插入排序：

1.从第一个元素开始，该元素可以认为已经被排序  
2.取出下一个元素，在已经排序的元素序列中从后向前扫描  
3.如果该元素（已排序）大于新元素，将该元素移到下一位置  
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  
5.将新元素插入到该位置中  
6.重复步骤2

[十分钟让你掌握插入排序][Link 3]

*  没有额外内存的申请和释放开销
 *  没有**递归栈**的开销（但对于非递归实现的呢？）

不过，更更关键的，当我们使用大O来描述算法的复杂度的时候，**是忽略常数项的**。大O刻画的是当数据规模无穷大的时候，算法性能的趋势。他只是一个趋势，不是精确的时间。我们说O(nlogn)的算法比O(n^2)的算法快，是因为当n无穷大的时候，哪怕O(nlogn)的算法是T = 1000000nlogn，而O(n^2)的算法是T = 2n^2，总有一个n，会使得1000000nlogn < 2n^2，并且随着n逐渐增大，这个差距越来越大（解方程，试试看这个n在哪里？）。**但是，当n比较小的时候，就不一定了比如n=8的时候，1000000nlogn = 24000000；而2n^2只有128**

插入排序法就是**一个常数项非常小的排序算法**，小于大多数排序。同时，对于有序（或者近乎有序）的数据，**插入排序还可以进化成为O(n)的算法**（因为第二层循环可以提前终止），而小数据量的数组，拥有**更高的概率是有序**的。所以，可以作为在数据量比较低的时候的一种**优化手段**。

> 不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。  
　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。  
　**快速排序是目前基于比较的内部排序中被认为是最好的方法**，当待排序的关键字是随机分布时，快速排序的平均时间最短；  
　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。  
　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

优先队列通常用堆排序来实现

[6524741_1489243629314_792B9001DFB7D6F2C5286D786EDED619]: /images/20220515/464522ad6ab642bf933854c697bc3943.png
[Link 1]: https://www.cnblogs.com/c4isr/p/4603980.html
[STL sort]: https://www.cnblogs.com/fengcc/p/5256337.html
[Link 2]: https://blog.csdn.net/fbp1040791153_/article/details/37322273
[Link 3]: https://www.cnblogs.com/shihaokiss/p/5449011.html