附录：所有blog的链接

数据结构学习笔记（1）：基本概念
数据结构学习笔记（2）：线性结构
数据结构学习笔记（3-5）：树
数据结构学习笔记（6-8）：图
数据结构学习笔记（9-10）：排序
数据结构学习笔记（11）：散列查找
数据结构学习笔记（12）：综合习题选讲

第九讲 排序（上）

9.0 概念

定义函数头：

void X_Sort（ElementType A[]，int N）

ElementType A[] 任意类型的数组

int N 长度

前提条件

大多数情况下，为简单起见，讨论从小大的整数排序

N是正整数

只讨论基于比较的排序（比较的符号>=<，有义）

只讨论内部排序，假设内存足够大能完成数据的一次导入

稳定性：任意两个相等的数据，排序前后的相对位置不发生改变

没有一种排序是任何情况下都表现最好的（所以需要多种不同的算法适用于多种不同情况）

9.1 简单排序（冒泡、插入）

逆序对的定义

对于下标$i<j$，如果$A[i]>A[j]$，则称$(i，j)$是一对逆序对（inversion）

冒泡排序

为了避免在排完后的重复检查，如果发现在过程中没有发生交换（flag没有产生变化），那么就认为已经完成了排序，跳出循环。flag也不是一定要加的。

优势：

可以使用与链表数组等数据结构，别的方法可能不适用于链表。

备注：

冒泡排序是稳定的，当元素相等的时候不需要交换。

执行交换的次数等于逆序对的个数。

插入排序

优势：

如果逆序对较少，可以做到简单高效，$O(N+I)$

备注：

插入排序是稳定的，当元素相等的时候不需要交换。

执行交换的次数等于逆序对的个数。

时间复杂度下界

定理： 任意$N$个不同元素组成的序列平均具有$N(N-1)/4$个逆序对。

定理： 任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$\Omega (N^2)$。

这意味着：要提高算法效率，我们必须今每次消去不止1个逆序对！每次交换相隔较远的2个元素！

9.2 希尔排序

增量序列的引入：试图解决一次交换只能消灭一个逆序对的问题

9.3 堆排序

算法1

通过堆一个一个赋值到数组中达到排序的效果

算法2

直接在堆中进行交换不需要重新申请存储空间

9.4 归并排序

主要适用范围外排序

核心：有序子列的归并

递归算法实现归并排序

在外部申请内存的原因：因为需要申请释放内存很多次，还不如直接申请一次并规定使用的指针反胃

非递归算法实现归并排序

第十讲 排序（下）

10.1 快速排序

大规模随机数据表现最好

核心思想

分而治之

算法想法：

随机选出一个主元然后根据主元分成两个部分

主元选取：

随机数的产生也有较高复杂度

所以采用取头尾中间三个数的中位数作为主元

子集划分：

所有的元素访问一遍，控制复杂度

快速排序之所以快的很重要原因：主元在子集划分过程中，直接完成了放置到正确位置的任务（左边的全比他小，右边的全比他大）。

划分子集时遇到与主元相同的元素情况处理方法：

进行交换

• 每次都进行交换，交换完后$i,j$会相互靠近，$i,j$最后会停在比较中间的位置，主元会被换到中间的位置，原始序列会被尽可能的等分成两个等长序列
• 相同元素较多时，产生很多附加的不要交换
• 不稳定的

不管，不进行交换

• 避免不必要交换
• 可能会由于相同元素过多，导致划分的两个子集有严重的数据量上的偏差eg.全1序列

小规模数据排序

快速排序使用递归。对小规模的数据（例如N不到100）可能还不如插入排序快。

解决方案：当递归的数据规模充分小，则停止递归，直接调用简单排序（例如插入排序）

10.2 表排序

定义

使用间接排序：不移动原始数据，实际只移动指针的排序方法

在物理存储上完成排序：每一个环开始时把数据存到temp里面，然后循环把下方的指针所指向的数据（应该存放在这里的数据）放入到这位置，并把下方table中的指针更新为当前所在位置（因为这个位置存储的数据已经是他应该在的位置了），再去下一个空位置。最后一个数据会经历判断环结束即为它指向位置那个存储空间已经是正确摆放了，怎么判断正确摆放呢自己的指针指向自己。

10.3 基数排序

桶排序

基数排序

多关键字排序

10.4 排序算法的比较

前三种排序是简单排序方法，容易实现

希尔排序的$d$取决于增量的设置

堆排序前面的系数较大

快速排序需要一个空间但是前面的稀疏较小