导图社区 第七章排序
第七章排序的思维导图，排序就是重新排列表中元素，是标中的元素满足按关键字有序的过程。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
第七章排序
排序的基本概念
排序，就是重新排列表中元素，是标中的元素满足按关键字有序的过程
评价指标
算法的稳定性，关键字相同的两个元素，在排序前后的相对位置不变，则这个排序算法是稳定的，否则是不稳定的
时间、空间复杂度
排序算法
内部排序
关注如何使算法的时间复杂度和空间复杂度更低
外部排序
还要关注如何使读写磁盘次数更少
选择排序
简单选择排序
算法思想
一种直观的排序算法
思想：是在未排序的序列中选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，以此类推
性能分析
空间复杂度:O(1)
时间复杂度:O(n²)
稳定性:不稳定
适用性:顺序表,链表都可以
堆排序
利用堆这种数据结构所设计的一种排序算法
核心思想：利用最大堆(或者最小堆）输出堆顶元素，即最大值（或最小值），将剩余元素重新生成最大堆（最小堆），继续输出堆顶元素，重复此过程，知道全部元素都已输出，得到的输出元素序列即为有序序列
插入排序
简单插入排序
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
空间复杂度:o(1）
时间复杂度
最好时间夏杂度:O(n)
最坏时间复杂度:O(n²)
平均时间复杂度:O(n²)
算法稳定性:稳定
优化
折半查找找到应插入的位置,仅适用于顺序表
注意:一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1)
比起直接插入排序,只减少了比较关键字的次数，时间复杂度仍是O(n)
希尔排序
先追求表中元素部分有序,再逐渐逼近全局有序
先将待排序表分割成若干形如L[i,i+d,i+2d....i +kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增里d,重复上述过程,直到d=1为止。
时间复杂度:和增里序列的选择有关，目前无法用数学手段证明确切的时间复杂度,但优于插入排序
算法的稳定性:不稳定
适用性:仅可用于顺序表
交换排序
冒泡排序
从后往前（或从前往后〉两两比较相邻元素的值，若为逆序《即A[i-1]>A[i]),则交换它们,直到序列比较完。称这样过程为“一趟”冒泡排序。最多只需n-1趟排序
每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再次对比
如果某―趟排序过程中未发生“交换”，则算法可以提前结束
每次交换都要移动元素三次
快速排序
在待排序表L[1...n]中任取一个元素pivot作为枢轴(或基准，通常取首元素）,通过―趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k:-1]中的所有元素小于pivotsL[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程,直至每部分只有一个元素或空为止，即所有元素放在了其最终位置上
算法表现主要取决于递归深度,若每次“划分"”越均匀，则递归深度越低
空间复杂度
最好:O(n)
最坏:O(log n)
最好:O(n²)
最坏:O(n log n)
平均:O(n log n)
归并排序
把两个或多个已经有序的序列合并成一个
2路归并的“归并树”——形态上就是一棵倒立的二叉树
n个元素进行2路归并排序,归并趟数=[log n]
实现步骤
若low<high，则将序列从中间mid=(low+high)/2分开
对左半部分[low.mid]递归地进行归并排序
对右半部分[mid+1,high]递归的进行归并排序
将左右两个有序子序列Merge为一个
空间复杂度:O(n)
每趟归并的时间复杂度:O(n)
算法的时间复杂度:O(n log n)
稳定性:稳定
基数排序
基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的)，借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD）排序和最低位优先(LSD)排序。
将整个关键字拆分为d位(或“组”)
按照各个关键字位权重递增的次序(如:个、十、百)，做d趟“分配”和“收集”，若当前处理的关键字位可能取得r个值，则需要建立r个队列
分配:顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
收集:把各个队列中的结点依次出队并链接。一趟收集耗时O (r)
分类
桶排序
单关键字的基数
空间复杂度:o(r)
时间复杂度:O(d(n+r))
适用性:善于处理
优点
1.数据元素的关键字可以方便地拆分为d组:且d较小
2.每组关键字的取值范围不大，即r较小
3.数据元素个数n较大
外部排序的原理
概念
需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。
内存容量无法容纳大量数据
使用“归并排序”的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序
外部排序:数据元素太多，无法一次全部读入内存进行排序
若要进行k路归并排序,则需要在内存中分配k个输入缓冲区和1个输出缓冲区
步骤
生成r个初始归并段（对L个记录进行内部排序,组成一个有序的初始归并段)
进行S趟k路归并,S=[]
k越大,r越小，归并趟数越少，读写磁盘次数越少
如何进行k路归并
把k个归并段的块读入k个输入缓冲区
用归并排序""的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中
每当一个输入缓冲区为空时,立即输入下一块待抖崴数据当输出缓冲区满时，写出外存
外部排序时间开销
读写外存的时间
内部排序所需时间
内部归并所需时间
优化思路
多路归并
需要增加相应的输入缓冲区
每次从k个归并段中选一个最小元素需要（k-1）次关键字对比
采用多路归并可以减少归并趟数,从而减少磁盘IO(读写)次数
减少初始归并段数量
若能增加初始归并段长度,则可减少初始归并段数量r
按照本节课介绍的方法生成的初始归并段，若共有N个记录，内存工作区可以容纳L个记录,则初始归并段数量r=N/L
纠错:k路平衡归并
1.最多只能有k个段归并为一个
2.每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到[m/k]个新的归并段
分析
读写外存的时间+内部排序所需时间+内部归并所需时间
多路归并带来的负面影响
k路归并时，需要开辟k个输入缓冲区，内存开销增加
每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加
如何得到初始的归并段
置换选择排序:解决排序段放入内存的问题，让初始归并段尽可能的少
如何减少多个归并段的归并次数
最佳归并树:最少的归并次数(I/O次数)
如何每次k路归并快速得到最小的关键字
败者树:减少关键字比较次数
一次划分≠—次排序
