排序算法总结-数据结构与算法教程

内容摘要
1. 排序汇总 类别排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况插入排序直接插入O(n^2)O(n)O(n^2)O(1)稳定希尔排序O(n^2)O(n)O(n^2)O(1)不稳定选择排序直接
文章正文

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. 发散性思维

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

 

代码注释
[!--zhushi--]

作者:喵哥笔记

IDC笔记

学的不仅是技术,更是梦想!