数据结构(8):排序

1 排序的基本概念

稳定性！！！

分类[内部、外部]

机械硬盘的读取是很慢的！！！

总结

2 内部排序

2.1 插入排序

前面时 保存好的 是排好序的哦 一个一个检查！然后放到改在的位置

只有小的时候换，等于的时候不换，这样可以保证算法的稳定性

代码实现：

代码实现(哨兵)【no没上一个清晰】

哨兵用于存储 要挪的元素！相当于上一个算法里的temp

两个算法复杂度和稳定性：

时间复杂度：

优化-折半插入序列：

一般数字：

相同的数字

low>heigh 是停止折半查找！

这个时候low右边的都大于插入值！A[0]复制到low所在的位置！

当A[mid]的值等于要插入的值的时候不要停止！应该再右边继续查找

代码实现：

时间复杂度：

对链表进行插入排序

好就好在 移动元素的次数变少了，因为在这里是指针 只需要动指针就可以了

但是时间复杂度还是那样！

总结

2.2 希尔排序

这样的话 插入排序的效率就会高一点！

总结：

常考：

算法实现【交替】：

在第二趟的时候，一个子表里有好几个元素，算法实现的时候不是一个一个子表单独排序的而是交替进行的！！！

主要是++i这句哦！！！i 指针一次只加1

复杂度

稳定性：

不适用于链表的实现！

总结：【代码不太考！】

2.3 交换排序

2.3.1 冒泡排序

每一趟都会使最小的数冒在前面！

相同的话不冒 保证算法的稳定性

算法实现

算法性能：

冒泡在链表里

总结：

没有发生交换，算法就结束！！！！flag变量！！

2.3.2 快速排序

不断地划分！

算法过程

根low指向的元素49比，49现在就是基准或者说是枢轴！

low 和high向中间移动！

此时low是空的 所以high向左移动！

这是小了就换！这是high空了

所以low向右移动 这个过程一直持续到 low=high时，把49放进去然后结束！

第一次结束之后49一定在正确的位置，所以对左右两个子表递归的调用 ！

不断地划分  最后  ok啦

代码：

递归调用栈：理解的时候注意标上#表示第几行 和传入的参数是多少！

算法效率：

空间复杂度：

组织成二叉树 就可以知道递归调用的层数！！！！

最好最坏时间、空间复杂度：

最坏的情况：

优化：

完全有序和逆序的时候 效率最差！！！

稳定性：

一次划分 指的是对连续表的快速排序

一趟排序 指的是一层quicksort 即从第一层到第二层这样！

一次划分可以确定一个元素的位置，一趟排序也许可以确定多个元素的位置！

2.4 选择排序

2.4.1 简单选择排序

找到最小的放在头部的位置：

代码实现：

复杂度:

稳定性：

总结：

时间复杂度不会因为所给序列特点不同而出现不同的时间复杂度！

对于n个序列就要进行n-1次对比

2.4.2 堆排序！！

二叉树的顺序存储

堆定义：

堆排序时选择排序的一种

所以排序时 也是在每一趟的待排序元素中选取关键字最小(或最大)的元素加入有序子序列！

堆顶的元素时最大的 所以一切都变得很简单了

建立大根堆：

只检查所有的非终端结点【即不检查叶子节点！】

方法：

可以直接通过下标 找到孩子的坐标！！！ 小元素不断下坠！！！

从n/2向下取整 到1 反向找！

代码实现：

基于大根堆排序：

然后9 进行下坠：

然后回复成大根堆了：

第二趟：

最后一个元素进行互换，最后一个元素就是顺序表中的最后一个！

交换--下坠 重复--直到排好

而基于“小根堆”的时“递减序列”！

代码实现：

算法效率

建立初始堆：

！！！！！！！！建堆的过程，关键词对比的次数不超过4n,建堆的时间复杂度就是o(4n)

排序的算法效率

总的时间复杂度：

稳定性：

优先换左孩子！

不稳定例子：

不稳定！！！！！！！！

排序总结：

排序练习：

在堆中插入新元素：

插入表尾，和父节点 （n/2向下取整） 进行对比 下的话就上升一直这样直到不能上升为止！

在堆中删除一个元素

用最后一个元素代替删除的元素 然后进行下坠的操作！

直到不能下坠为止！

下下坠时 如果子节点有两个的话 要对比两次选出最！

堆插入删除总结

2.5 归并排序

两个有序的序列合并起来！

“n路”归并【对比关键字n-1次】

手算模拟

代码实现

用一个辅助数组B

辅助数组复制所有的要排序的数 过去！i j指针比较小的上去 同时++ k也++

最后两行

也是递归算法！

算法效率分析

最好最坏和平均的时间复杂度都是o(nlogn)

空间复杂度：

递归的空间复杂度呢？ 递归的空间复杂度是：o(logn)

稳定性：稳定！

总结

2.6 基数排序

第一趟：

按照个位递减的序列！

第二趟：

收集：

第三趟：

收集：

基数排序过程：【不是基于比较的算法，比较特别！】

算法效率分析

空间复杂度：

新增一个队列只是新增了一个指针域 空间复杂度是O(1)

时间复杂度：

稳定性：稳定！

基数排序的应用：

按照权重递增的顺序 进行拆分！

每一个关键字位数目不一定相同！！！1

擅长解决的问题：

总结：

链式存储：

3 外部排序

3.1 外部排序的基本概念

外存和内存之间的数据交换

是以块为单位进行排序的

外部排序的原理：

3块缓冲区！

1、构造初始“归并段”

读进去之后进行内部排序后得到！：

把输入1换到输出1

输入2 同理 

重复：得到归并段：

2、第一趟归并“归并段”

两个归并段的第一个字段 放到输入缓冲区 进行归并排序

放到输出缓冲区 满了就写磁盘 输入缓冲区1空的话就紧接着读归并段1 2空的话读2的   别乱着读1！！！

类似的对3、4  5、6  7、8 进行排序

经过第一趟8变4！

3、第二趟

一样的！！！

空了之后立即放入对应的归并段！

归并之后会写入外存的另一个空间中！！！不会在原地方！！

3 第三趟

时间开销分析

2的三次方等于(16/2) 所以需要对比 3次至少！！

优化1：减少归并的趟数【多路归并】

多路归并：

2 的平方 等于 （16/4） 所以需要两趟！！！！

多路归并的问题

优化2：减少初始归并段的数量！

则就能在原点相遇！

外部排序总结：

这里初始归并段完全取决于内存工作区有多大！

多路平衡归并

图和定义不一致：

所以K路平衡归并的定义如下：

因此上面这个例子是 四路归并排序 但不是4路平衡归并排序！

3.2 败者树【解决多路归并时间开销大】

败者树定义

败者树可以看作是 完全二叉树

败者树的使用：

派大星从他那一路打上去就可以，因为右边的谁强谁弱已经知道了

败者树在多路平衡归并中的应用：

多路平衡归并：

本来找到最小的需要进行7次对比！现在用每一个归并段的第一个形成一个败者树！

找到最小值！

记录编号即可，不用记住是谁！

1 是在归并段3里的，所以用归并段3的下一个元素从底部替代原来的，然后再进行对比！

第一趟构造败者树时，需要对比N-1次！！！

只要构成了败者树，下一次的关键词对比 只需要比败者树 分支层有多少层！高度的次数就可以！这样就大大的减少了！！！

1024路 本来每一次都需要1023次对比 用败者树10次就好！！！！

代码：【no考】

所以ls[0]对应的就是冠军！！！！

总结：

3.3 置换选择排序

初始归并段极可能的小

开始的方法：

在磁盘中那两个放入缓冲区！ 然后归并排序后放回磁盘！ 一共6个记录 行程里一个归并段！

如果想要归并段更长 可以让内存中多几个缓存区 同时归并好几个字段！

也就是说以前的方法说明：得到的初始归并段的数量是直接由 内存工作区WA的容量决定的！！！

怎末构造一个比内存工作区更大的归并段呢？--置换排序！！！

置换选择排序

1、读入找到最小【比之前大】拿出去 再读入

递增的话找个最小的让他出去！

记录出去的值的大小在minimax里，在读入一个新的

再找到最小的是6 而且6比minimax大 让6出去 并且把minimax的值改为6

重复。。。。

2、不符合条件了

除了10就是14最小比minimax的值大 把14拿出去！

重复。。。

直到。。

3、不符合的站买了 第一个归并段结束 解冻不符合 重复12找到第二个归并段！

归并段少--归并操作时的读写次数也就少了！

输入输出的时候不是像演示一样 一个一个读和写的 是有缓冲区的 也就是说一次读入一堆！

总结：

3.4 最佳归并树【K叉哈夫曼树！】

上面的置换选择排序的得到的初始归并段的长度不一 因此我们需要这个算法就是为了找到一个最好的方式 使得归并的时候读写磁盘的次数最少！

带权路径长度！：可以看树里的哈夫曼树

所以！！！！

因此按照构造哈夫曼树的方法构造最佳归并树即可！

多路归并时：

选出最小的合并一样的和哈夫曼树

如果减少一个归并段【减少30】【坑！！！】

这是不对的因为 最后一次归并不是三个是两个！！！！！

添加几个虚段！！

度为0的是叶子节点 相当于叶子节点

k*n_k表示的是分叉的叉的数量 

方法：

小练习：

总结：