知识点

1.基本概念

排序：就是一系列数据，按照某个关键字（例如：销量，价格），进行递增或者递减的顺序排列起来

排序的稳定性：能保证两个关键字相等的数，经过排序之后，其在序列的前后位置顺序不变。

内部排序：待排序记录全部存放在计算机内存中进行排序的过程称为内部排序；

外部排序：指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

2.插入排序

2.1、直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入已排好序的表，从而得到一个新的、记录数量增1的有序表。

时间复杂度：平均O(n²)，最好O(n)， 最坏O(n²)
空间复杂度：O(1)，因为只需要一个记录的辅助空间 r[0]

特点：

1. 稳定性：稳定
2. 也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针
3. 更适用与初始化基本有序的情况

2.2、折半插入排序

原理：折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法

步骤：
第一步：折半查找——用low、mid、high划分两个区域【low，mid-1】和【mid+1，high】
第二步：判断——如果key值小于序列的中间值【mid】，则代表key值应该插入左边的区域【low，mid-1】，然后对【low，mid-1】再重复划分区域，直到low>high为止
第三步：插入——最后的插入位置应该是high+1，我们只需要先将high之后位置的数据整体后移，然后将key赋值给【mid+1】，即完成插入。

时间复杂度：O(n²)
空间复杂度：仍是只需要一个记录的辅助空间r[0]，所以时间复杂度为O(1)

算法特点

1. 稳定排序。
2. 因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。
3. 适合初始记录无序、n较大的情况。

2.3、希尔排序

希尔排序（Shell’s Sort）又称“缩小增量排序”；实质上是采用分组插入的方法，先将整个待排序记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。

（1）第一趟取增量d1 = 5，所有间隔为5的记录分在同一组，全部记录分成5组，在各个组中分别进行直接插入排序，排序结果如图8.2的第7行所示。
（2）第二趟取增量d2 = 3，所有间隔为3的记录分在同一组，全部记录分成3组，在各个组中分别进行直接插入排序，排序结果如图8.2的第11行所示。
（3）第三趟取增量d3 = 1，对整个序列进行一趟直接插入排序，排序完成，排序结果如图8.2的第12行所示。

时间复杂度：n(log₂n)²
空间复杂度：也是只需要一个辅助空间 r[0] ，所以时间复杂度为O(1)

特点：

1. 稳定性：因为记录跳跃式地移动，所以不稳定
2. 只适用于顺序结构，不能用于链式结构
3. 适用于初始记录无序、n较大的情况

总结

3.交换排序

3.1、冒泡排序

冒泡排序（Bubble Sort）是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果为逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”（左移），或者使关键字大的记录如石块一样逐渐向下“坠落”（右移）。

---

时间复杂度为O(n²)，但若是一开始就是有序的，则时间复杂度为O(n)

特点：

1. 稳定性：稳定
2. 可以用于链式存储结构
3. 当初始记录无序，n较大时，此算法不宜采用

3.2、快速排序

快速排序（Quick Sort）是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序排列。如果能通过两个（不相邻）记录的一次交换，消除多个逆序排列，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序排列。

---

时间复杂度：O(nlog₂n)

空间复杂度：最好情况下的空间复杂度为：O(log₂n)，最坏情况下为O(n)

特点：

1. 记录非顺次的移动导致排序方法是不稳定的
2. 排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构
3. 当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况

总结

4.选择排序

4.1、简单选择排序

简单选择排序又称为直接选择排序；在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数中再找最小（或者最大）的与第2个位置的数交换，以此类推，直到 第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

---

---

时间复杂度：O(n²)

空间复杂度：同冒泡排序一样，只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1)

特点：

1. 稳定性：不稳定
2. 可用于链式存储结构
3. 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快

4.2、树形选择排序

树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中 n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。

4.3、堆排序

堆排序（Heap Sort）是一种树形选择排序，在排序过程中，将待排序的记录r[1..n]看成一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

堆是具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
• 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

总结：

5.归并排序

归并排序（Merging Sort）就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并；
思想是：假设初始序列含有n个记录，则可将其看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止。

总结：

6.基数排序

一般使用链式基数排序

从最低位（个位）开始进行，按关键字的不同收集，然后按第二低位（十位）开始进行，按关键字的不同收集，若有些数没有更低位，则按0收集

特点：

1. 稳定性：稳定排序
2. 可用于链式结构，也可用于顺序结构
3. 基数排序需要知道各级关键字的取值范围

总结

---

练习题

一、选择题

二、判断题

答案解析

一、选择题

二、判断题