数据结构第八讲课程笔记——排序
nets:[[../else/数据结构]] 课程笔记
8.1 概述
一、什么是排序？
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
二、内部排序与外部排序
若整个排序过程不霄要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
三、内部排序的方法
内部排序的过程是一个逐步扩大记录的有序序列长度的过程
内部排序的类型
8.2 传统排序
1.插入类
将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。
时间复杂度：O(n** 2)
2.交换类
通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。
时间复杂度：O（n** 2）
3.选择类
从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。
时间复杂度：O（n** 2）
8.3 希尔排序
8.4 快速排序
一、一趟快速排序
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
二、快速排序
8.5 堆排序
- 如何把完全二叉树变成堆？
假设二叉树的某个结点的左右子树都是堆，应该如何调整i,使以i为根结点的子树成为堆？
8.6 归并排序
归并排序的过程基于下列基本恩想进行：
将两个或两个以上的有序子序列“归并”为一个有序序列。
8.7 基数排序
基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。
一、多关键字的排序
最高位优先MSD法
先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，.，依次类推，直至最后对最次位关键字排序完成为止。
最低位优先LSD法
先对Kd1进行排序，然后对Kd2进行排序，依次类推，直至对最主位关键字K0排序完成为止。
排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若千个(“前一个”关键字不同的)子序列。
二、链式基数排序
假如多关键字的记录序列中，每个关键字的取值范围相同，则按 LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。
对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配一收集”的办法进行排序，称作基数排序法。
在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：
1.待排序记录以指针相链，构成一个链表；
2.“分配”时，按当前“关键字位”所取值，将记录分配到不同的”链队列”中，每个队列中记录的“关键字位”相同；
3.“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表；
4.对每个关键字位均重复2)和3)两步。
8.8 各种排序方法的综合比较
一、时间性能
1.平均的时间性能
2.最好情况下的时间性能
3.最坏情况下的时间性能
二、空间性能
指的是排序过程中所需的辅助空间大小
三、排序方法的稳定性能
1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。