数据结构复习之排序

数据结构复习之排序

目录

基本概念

插入排序

直接插入排序

希尔排序

交换排序

起泡排序

快速排序

 选择排序

简单选择排序

 堆排序

归并排序

---

基本概念

排序：将记录排列成某种顺序的序列。
(将任一个记录的任意序列重新排列成一个按关键码有序的序列。)

内排序：待排序的所有记录全部被放置再内存中。
外排序：待排序记录个数太多，不能同时放在内存内，一部分放在外存。

插入排序、交换排序、选择排序、归并排序

稳定性：稳定：经过排序，多个具有相同关键码的相对次序保持不变。

正序：待排序记录序列已经排好序。 逆序(反序)：与排好的顺序正好相反。

插入排序 直接插入排序

插入排序中最简单的排序方法。
想想打牌！！！
从无序区的第一个记录插入有序区的合适位置中。

最好情况的时间复杂度：O(n)  最坏情况：O(n2)   平均时间复杂度:O(n2) 
只需要一个记录的辅助空间暂存待插记录。  稳定。

若待排记录基本有序，直接插入的效率很高。待排序记录个数较少时效率也高。

希尔排序

对直接插入排序的改进。
基本思想：分割整体成若干个子序列，再在子序列内分别进行直接插入排序，待整个序列基本有序时再对全体记录进行一次直接插入排序。

增量序列，d=n/2  ......依次递推，增量序列互质且递减，最后一个增量必须为1。

 时间性能在O(nlog2n)&O(n2)之间。只需一个记录的辅助空间。 不稳定

交换排序 起泡排序

交换排序中最简单的排序方法。
基本思想：两两比较相邻记录，若反序则交换，直到没有反序的记录为止。
对无序区从前向后依次将相邻记录比较，值较小的记录向前移，值较大的记录向后移。

执行时间取决于排序趟数。
最好：只执行一趟，O(n)  最坏：O(n2)  只需一个记录的辅助空间，稳定。

快速排序

先选一个轴值(比较基准),划分待排序的记录。左侧<=轴值，右侧>=轴值。重复，直到序列有序。
选取轴值最简单的时选取第一个记录，最后一个记录和中间记录。

 选择排序 简单选择排序

最简单的选择排序

基本思想：第i趟排序在待排序序列中选取最小的记录，并和第i个记录交换作为有序序列的第i个记录。
初始时有序区为空，不断重复上述步骤直到无序区只剩下一个记录。

 

待排序列为正序，移动0次，待排序列为逆序，移动3(n-1)次

最好=最坏=平均=O(n2)，只需一个作为记录交换的暂存单元。 不稳定。

 堆排序

完全二叉树

小根堆：每个结点的值小于或等于左右孩子结点的值。
大根堆：每个结点的值大于或等于左右孩子结点的值。

一个完全二叉树如果是堆，则根结点(堆顶)一定是当前所有结点的最大者或最小者。以结点的编号作为下标，将堆用顺序存储结构存储。

运行时间主要消耗在初始建堆&重建堆时进行的堆的调整。
初始建堆O(nlog2n)，第i次重建堆O(log2i)。
总的时间复杂度：O(nlog2n)
堆排序对排序的初始状态不敏感(相对于快速排序的最大优点)
只用一个用来交换的暂存单元，不稳定。

归并排序

将待排序序列划分为两个长度相等的子序列，分别对两个子序列排序，再合并。

 时间复杂度：O(nlog2n) ,空间复杂度：O(n), 稳定

//大概写了一点简单的，凑合看看8！