20-数据结构与算法-04-排序
排序
排序基本概念
-
排序就是将一组数据元素序列重新排列，使得数据元素序列按某个数据项（关键字）有序。
排序依据：是依据数据元素的关键字
若关键字是主关键字（关键字值不重复），这无论采用何种排序方法，排出的结果都是唯一的；
若关键字是次关键词（关键字值可以重复），则排出的结果可能不唯一。
稳定排序和不稳定排序
内部排序和外部排序
- 若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序；
- 反之，若参见排序的记录数量很大，整个排序过程不可能在内存中完成，则称此类排序为外部排序。
插入排序
基本思想
将无序子序列中的一个或几个记录“插入”到有序子序列中，从而增加有序子序列的长度。
实现一趟插入排序可分三步进行：
分类
- 直接插入排序（基于顺序查找定位）
- 折半插入排序（基于折半查找定位）
- 希尔排序（基于逐趟缩小增量）
直接插入排序
排序过程
整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。
算法描述
算法性能
==分析结果显示：用直接插入排序，数据序列越接近有序，比较次数越少。==
希尔排序
基本思想
分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。
对待排记录序列先做宏观调整，再做微观调整。
宏观调整指的是“跳跃式”的插入排序
排序过程
- 首先将记录序列分成若干个子序列；
- 然后分别对每个子序列进行直接插入排序；
- 最后待基本有序时，再进行一次直接插入排序。
其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直到最后一趟排序减为1。
排序特点
最坏复杂度分析
Hibbard's增量序列
算法性能
选择排序
简单选择排序
基本思想
从无序子序列中选择关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列长度。
排序过程
- 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；
- 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；
- 重复上述操作，共进行n-1趟排序后，排序结束。
算法描述
性能分析
算法评价
稳定性分析
归并排序
合并2个有序表
归并
将两个或两个以上的有序表组合成一个新的有序表，叫归并排序
排序过程
设初始序列含有n个记录，可以看做n个有序子序列，每个子序列长度为1，两两合并，得到二分之n个长度为2或1的有序子序列，再两两合并，。。。。。如此重复，直至得到长度为n的有序序列为止。
迭代算法
- 将序列的每一个数据看成长度为1 的有序表；
- 然后将相邻两组进行归并得到长度为2的有序表（一趟归并）；
- 再对相邻两组长度为2的有序表进行下一趟归并得到长度为4的有序表；
- 如此一直进行下去，直到整个表归并成有序表。
如果某一趟归并过程中，单出一个表，该表轮空，等待下一趟归并。
递归思想
将无序序列划分成大概均等的2个子序列，然后用同样的方法对2个子序列进行归并得到2个有序的子序列，再用合并2个有序表的方法合并这2个子序列，得到n个元素的有序序列。
算法描述
算法评价
交换排序
通过交换无序序列中的记录从而得到其中关键字最大或最小的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列长度
- 冒泡排序
- 快速排序
冒泡排序
排序过程
代码实现
算法评价
算法优化
- 冒泡排序的结束条件为最后一趟没有进行交换记录
- 一般情况，每经过一趟冒泡，m-1，但并不是每趟都是如此。
快速排序
算法思想
枢纽
排序过程
算法实现
算法评价
三者取中法
算法特点
算法分析
基数排序
多关键字排序
高位优先多关键字排序
低位优先多关键字排序
==低位优先多关键字排序的实现更加简单，每趟排序都是一样无差别的操作，只不过排序因子不一样。==
链式基数排序
顺序基数排序
外部排序
大多数内排序算法都是利用了内存是直接访问的事实，读写一个数据是常量的时间。如果输入是在磁带上，磁带上的元素只能顺序访问，甚至数据是在磁盘上，效率还是下降。因为转动磁盘和移动磁头会产生延迟。
- 外排模型
- 预处理
- 归并
外排序模型
- 外排序具有设备依赖性。这里考虑的算法工作在磁带上；
- 完成有效的排序至少需要两个磁带机；
- 三个磁带机可以简化问题
外排序的基本方法
- 由于一次外存操作所需的时间可以执行数百条甚至上千条指令，因此在外排序中我们考虑的是如何减少外存储器的读写；
- 在外存上进行排序的最常用的方法就是利用归并排序，因为归并排序只需要访问被归并序列中的第一个元素，这里非常适合于顺序文件；
- 外排序由两个阶段组成：
- 预处理阶段：根据内存的大小将一个有n条记录的文件分批读入内存，用各种内排序算法排序，形成一个个有序片段；
- 归并阶段：将这些有序片段逐步归并成一个有序文件。
预处理阶段
归并阶段
- 两路归并
- 多路归并
- 多阶段归并
