8/8 排序
8.1 基本概念
自然排序:输入数据越有序,排序的速度越快的排序方法。
内存排序:排序时只用到内存没有用到外存
串行排序:单个处理器,而非多个同时进行
比较排序:用比较的方法
8.2 插入排序
8.2.1 直接插入排序
8.2.2 二分插入排序
8.2.3 希尔排序:不稳定
8.3 交换排序
8.3.1 冒泡排序
- n个记录,总共需要n-1趟
第m趟需要比较n-m次
小改进,如果某一趟没有发生交换,说明已经排序完毕。
8.3.2 快速排序
升级快速排序:不用单独开辟存放子表的空间,但是因为递归需要建立栈
①每一趟的子表的形成是采用从两头向中间交替式逼近法;
②由于每趟中对各子表的操作都相似,可采用递归算法。
- 划分元素的选取是影响时间性能的关键
输入数据次序越乱,所选划分元素值的随机性越好,排序速度越快,快速排序不是自然排序方法。
改变划分元素的选取方法,至多只能改变算法平均情况的下的时间性能,无法改变最坏情况下的时间性能。即最坏情况下,快速排序的时间复杂性总是O(n2)
8.4 选择排序
如何从无序数列生成堆呢?
单结点的二叉树是堆;
在完全二叉树中所有以叶子结点(序号i > n/2)为根的子树是堆。这样,我们只需依次将以序号为n/2,n/2 - 1,…1的结点为根的子树均调整为堆即可。
因为堆顶始终是最小(大)值,所以每次都输出根节点,然后进行调整。不断输出的根节点就可以组成一个有序序列。
堆排序方法对初始序列没有依赖性,初始有序无序所花时间空间没有多少变化
8.5 归并排序
8.6 基数排序
选取多个关键字,优先级低的先分配收集,优先级最高的最后进行分配收集。
有趣的例子:对打乱的扑克牌进行排序
先根据花色进行分配收集,后根据点数进行分配收集。最后得到点数从小到大并且同一点数的牌都按相同花色顺序排列。
综合比较
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClancyCC!
评论