排序算法总结

点击打开在线编译器,边学边练

1. 排序汇总

 

类别

排序方法

时间复杂度

空间复杂度

稳定性

平均情况

最好情况

最坏情况

插入排序

直接插入

O(n^2)

O(n)

O(n^2)

O(1)

稳定

希尔排序

O(n^2)

O(n)

O(n^2)

O(1)

不稳定

选择排序

直接选择

O(n^2)

O(n^2)

O(n^2)

O(1)

不稳定

堆排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

不稳定

交换排序

冒泡排序

O(n^2)

O(n)

O(n^2)

O(1)

稳定

快速排序

O(nlogn)

O(nlogn)

O(n^2)

O(nlogn)

不稳定

归并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

稳定


2.各个排序面对数据的适用情况与小技巧

选取几个比较有特点有代表性质的排序算法

快速排序算法的效率体现在序列越乱的时候,效率越高,当数据趋于一个有序状态时(无论是顺序还是逆序),将会退化为冒泡排序,当数据完全处于逆序状态时,快速排序将会消耗极大的时间,因此有些OJ的快速排序模板测试题并不能直接写快排通过【毒瘤数据,超大完全逆序数据】,可以尝试适用rand()产生随机数的方法将整体数据打乱再使用快速排序,可以极大的减少运行时间。

直接插入排序有着稳定和速度快的优点,缺点是比较次数越少,插入点后的数据移动就越多,特别是数据庞大的时候就需要大量的移动数据。

堆排序作为一个相对比较复杂的排序,我们可以更加深入的去借鉴思想,比如有问题要求在n个数据中选出或者排序出前k个数据,利用堆排序的思维可以不将全部的n进行排序而只操作出前k个数据的情况,这个思维是很重要的。

希尔排序最主要的操作是比较而不是交换,因此在小数组的情况下是比快速排序和堆排序要快的,但是涉及大量数据时依旧不如快排。

对于绝大多数排序在数据达到顺序的情况下并没有办法直接结束,在前置处理数据不是很大的情况下,可以设置一个flag标记,当数据完全处于顺序的情况下直接强制退出排序,以达到减少运行时间的效果,当然前置处理数据在总执行步骤中占比不易过大,如总执行100次,在执行95次的时候已经达到顺序,有5次循环浪费,这样的情况浪费时间不如你而外增添的标记判断时间,就不需要这个flag标记。


3. 发散性思维

上面我们对比切了解到了各种排序的应用情况及优缺点,任何一种排序都不是十全十美的,因此我们最好的方式就是扬长避短,那么请你设计一个算法,能够主动的通过一次遍历去发现数据的情况,究竟最适合何种排序为妙呢?

 

 

 

 

 

 

 

 

 

 


上一课:快速排序
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记