数据结构3:查找与排序

ch8.查找

8.1 查找算法的评价指标(ASL)

查找长度：在查找运算中，需要对比关键字的次数称为查找长度；

平均查找长度（ASL，Average Search Length）：所有查找过程中进行关键字的比较次数的平均值。

$ASL = {\sum\limits_{i = 1}^{n}{P_{i}C_{i}}}$（$P_{i}$为查找第i个元素的概率，$C_{i}$为查找第i个元素的查找长度，n为数据元素个数）

查找主要分为基于比较的查找和基于位置的查找（哈希表）。

8.2 静态查找表

8.2.1 顺序查找

0号位置添加哨兵（sentry）实现：

typedef struct
{
    ST.elem[0]=key;		//"哨兵"
    int TableLen;		//表的长度
}SSTable;

int Search_Seq(SSTable ST,ElemType key)				//顺序查找
{
    ST.elem[0]=key;		//0号位置存“哨兵”
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i){}		//从后往前找
    return i;			//查找成功，则返回元素下标；查找失败，则返回0
}

查找效率分析：

${ASL}_{成功} = \frac{1 + 2 + 3 + \ldots + n}{n} = \frac{n + 1}{2}$（第一个查找到花1次，第二个花两次，以此类推），时间复杂度为$O(n)$。

注：

• 平均查找长度也可以这样表示：$ASL_{成功}=\sum_{i=n}^{1}(n-i+1) / n=(n+1) / 2$；

• 若存在查找失败的情况，则需要另外进行讨论。

若顺序查找思想放在有序表中，表中元素有序存放（递增/递减），若……，则说明查找失败。

一个成功结点的查找长度=自身所在层数；一个失败结点的查找长度=其父结点所在层数。

默认情况下，各种失败情况或成功情况都等概率发生。

若各个关键字被查概率不同，可按照被查概率降序排列，这样可以使查找成功时ASL更少。

8.2.2 折半查找

又称“二分查找”，仅适用于有序表的查找（有序表在计算机学科中默认正序）。

int Binary_Search(SSTable L,ElemType key)
{
    int low=0,high=L.TableLen-1,mid;
    while(low<=high)
    {
        mid=(low+high)/2;		//取中间位置
        if(L.elem[mid]==key)
            return mid;			//查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1;			//从前半部分继续查找
        else
            low=mid+1;			//从后半部分继续查找
    }
    return -1;
}

折半查找判定树的构造：(基于位置)

注：若基于数据，则是一个中序有序的二叉树。

在判定树中，称方形结点为判定树的外部结点；与之相对，称那些圆形结点为内部结点（在离散数学中，称上述两种结点分别表示两个类型[等价类]）。

如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等；

如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素。

【注意】每轮判断mid值时，需变动low值为mid+1或high值为mid-1。

折半查找的判定树中，若$mid = \left\lfloor {\left( low + high \right)/2} \right\rfloor$，则对于任何一个结点，必有右子树结点数-左子树结点数=0或1。

折半查找的判定树一定是平衡二叉树。

折半查找的判定树中，只有最下面一层是不满的，因此当元素个数为n时，树高$h = \lceil log_{2}\left( n + 1 \right) \rceil$（不包含失败结点）。

查找成功时折半查找的平均查找长度

$\begin{aligned}
ASL_{success} &=\sum_{i=1}^{n} P_{i} C_{i} =\frac{1}{n} \sum_{j=1}^{h} j \cdot 2^{j-1} =\frac{n+1}{n} \log _{2}(n+1)-1
\end{aligned}$

当n较大时，可得到近似结果：$\begin{aligned}
ASL_{success} =\log _{2}(n+1)-1
\end{aligned}$

折半查找实现代码如下：

//  Performs the standard binary search 
//  Returns index where item is found, or -1, if not found.     
int BinarySearch(const int a[], const int x, int n) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] < x)
            low = mid + 1;
        else if (a[mid] > x)
            high = mid - 1;
        else
            return mid; 	  // Found
    }
    return NOT_FOUND;
}

8.2.3 插值查找

插值查找（interpolation search）实际上是二分查找的改良版。在插值查找中，可以改变二分查找的区间缩减策略，根据搜索的值来确定区间缩减幅度，其中间位置的计算公式如下：$mid=left+alpha\times(right-left)$，其中alpha用于衡量搜索目标值距离左边界的远近。将alpha的表达式代入，即有：$mid=\left\lfloor\frac{(k e y-A[l])(r-l)}{A[r]-A[l]}\right\rfloor$，其中l和r分别代表数组的第一个和最后一个索引，key代表待查找的元素。

当一次查找失败时，若目标值在中间值右边，更新左边界位置；若目标值在中间值左边，更新右边界位置。

假设有这样一个数组 $[0,10,20,30,40,50,60,70,80,90]$ ，我们可以发现，每个相邻元素的差均为10，满足均匀分布。此时只要一次就能找到我们要找的元素。

插值查找实现代码如下：

int InterpolationSearch(int *D, int dataLength, int targetValue) {
	int left = 0;
	int right = dataLength - 1;
	int mid;
	// 终止条件
	while (left<right)
	{
		// 中间位置计算
		mid = left + int((targetValue-D[left])/(D[right]-D[left])*(right-left));
		if (*(D + mid) == targetValue) {
			return mid;
		}
		// 目标值在中间值右边，更新左位置
		else if (*(D + mid) < targetValue){
			left = mid + 1;
		}
		// 目标值在中间值左边，更新右位置
		else
		{
			right = mid - 1;
		}
	}
	// 只剩最后一个元素时
	if (left == right) {
		if (targetValue == D[left]) {
			return left;
		}
	};
	// 搜索不到，返回-1
	return -1;
}

8.2.4 索引顺序表的分块查找

分块查找又称索引顺序查找。该查找算法中，除表本身以外，还需建立一个“索引表”，索引顺序表分块有序，每个子表中所有记录的关键字均大于上一个子表中的关键字。

索引顺序查找分两步：

• 确定待查找的记录所在的块（子表），然后在块中顺序查找；需根据给定值key与索引表中的最大关键字作比较
• 对子表中的记录进行顺序查找

算法中，对索引表的查找可以采用顺序查找或折半查找。

sequentially search index and data table：

$\begin{array}{l}
A S L=L_{b}+L_{w} =\sum_{j=1}^{b}(j / b)+\sum_{j=1}^{S}(i / s) =(b+1) / 2+(s+1) / 2=(b+s) / 2+1
\end{array}$

binary search index table, sequentially search data table：

$A S L=\log _{2}(n / s+1)+s / 2$

8.3 二叉排序树(BST)

下面介绍的是动态查找表的表示和实现。二叉排序树，又称二叉查找树（BST，Binary Search Tree），在该树中，左子树结点值均小于根结点值，右子树结点值均大于根节点值（假定子树非空），且它的左右子树也分别是二叉排序树。

对该树进行中序遍历，可以得到一个递增的有序序列。

8.3.1 查找

查找算法中，成功，返回结点位置；失败，返回左/右孩子，算法实现如下：

Status SearchBST(BiTree T, KeyType key, BiTree& f, BiTree& p) {
    // IF SEARCH IS SUCCESS p points the node,else p points to the last node in the visiting path,f is the parent of T，initial value is NULL
    if (!T) {
        p = f; return FALSE;
    } //failure
    else if (EQ(key, T->data.key)){
        p = T; return TRUE;
    } // sucess
    else if (LT(key, T->data.key))
        SearchBST(T->lchild, key, T, p);
    else SearchBST(T->rchild, key, T, p);
} // SearchBST

查找效率分析：

​ 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而**具有n个结点的二叉排序树的深度，最好为$log_{2}n$，最坏为$n$**。因此，二叉排序树查找的最好时间复杂度为$O(log_{2}n)$，最坏的时间复杂度为O(n)。一般情形下，其时间复杂度大致可看成$O(log_{2}n)$，比顺序查找效率要好，但比折半查找要差。

8.3.2 插入

若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。该算法是递归实现的，故最坏的空间复杂度为**O(h)**（h为树的高度）。

void insertBST(BST, s)
{
	p = BST;
	while (p)
	{
		parent = p;
		if (s->data < p->data) p = p->lc;
		else   p = p->rc;
	}
	if (parent == NULL)				//整棵树是空的，该结点直接作为树根返回
		BST = s;
	else if (s->data < parent->data)
		parent->lc = s;
	else parent->rc = s;
} // Insert BST

8.3.3 删除

先搜索找到目标结点，然后分以下三种情况进行删除操作：

（1）若被删除结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质（即左子树结点值<根结点值<右子树节点值）；

（2）若结点z只有一棵子树（左子树或右子树），则让z的子树成为z父结点的子树，替代z的位置；

也可以使用替身的做法[第三种情况也需使用替身]：

将数据data搬上去，然后将可能的左/右子树作为它的左/右子树，这样不需要改动与双亲之间的关系。

（3）若结点z有左、右两棵子树，则用另一结点替代被删除的结点x[复制数据域]：x可为右子树的最小元素或者左子树的最大元素[后面使用的是第一种]，然后删除这个替代结点（因为在二叉排序树中右子树的最小元素、左子树的最大元素要么是叶子结点，要么只有一棵左子树或右子树，一定不会同时有左、右子树，这样就转换成了第一或第二种情况）；

[注]进行中序遍历，可以得到一个递增的有序序列，故z的后继即为z的右子树中最左下结点（该结点一定没有左子树，然后可以参考第二种情况）。

删除算法代码实现如下：

BSTree Delete(BSTree BST, int x)
{
	BSTNode *p;
	if (BST == NULL) //如果树为空直接返回
		return NULL;
	else if (x < BST->data) //小于则左子树递归删除
		BST->lchild = Delete(BST->lchild, x);
	else if (x > BST->data) //大于则右子树递归删除
		BST->rchild = Delete(BST->rchild, x);
	else //等于则找到了要删除的结点
	{
		//如果被删除的结点有左、右两个孩子结点
		if (BST->lchild && BST->rchild)
		{
			//找到右子树的最小元素
			p = FindMin(BST->rchild);
			//替代被删除的结点
			BST->data = p->data;
			//在被删除结点的右子树中删除刚才找到的右子树的最小元素
			BST->rchild = Delete(BST->rchild, p->data);
		}
		//如果被删除结点只有一个孩子结点或没有孩子结点
		else
		{
			p = BST;
			if (BST->lchild == NULL)		  //有右孩子结点或没有孩子结点
				BST = BST->rchild;
			else if (BST->rchild == NULL) 	  //有左孩子结点
				BST = BST->lchild;
			free(p); //释放结点
		}
	}
	return BST;
}

BSTree FindMin(BSTree BST)
{
	if(BST == NULL) //树为空直接放回
		return NULL;
	else if(BST->lchild == NULL) 	//找到最左叶子结点并返回
		return BST;
	else
		return FindMin(BST->lchild); //沿左分支继续递归查找
}

查找、插入、删除的时间复杂度分析：

	unsorted array	sorted array	linked list	BST
insert	find + O(n)	O(n)	find + O(1)	O(Depth)
find	O(n)	O(log n)	O(n)	O(Depth)
delete	find + O(1)	O(n)	find + O(1)	O(Depth)

8.4 平衡二叉树(AVL)

8.4.1 平衡二叉树的定义

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树），其树上任一结点的左子树和右子树的深度之差的绝对值不超过1。

结点的平衡因子BF（Balance Factor）=左子树的深度-右子树的深度。

平衡二叉树结点存储结构的定义：

typedef struct AVLNode{
    int key;		//数据域
    int balance;	//平衡因子
	struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

降低BST的高度，有以下两种方法：

• 平衡化：
  • AVL Tree
  • Red-Black（红黑树）
  • Splay Tree（伸展树）
• m-ary查找树

调整二叉树，使之称为AVL Tree有以下两个关键步骤：

• 找到最小非平衡子树的树根

  特点：==离插入点最近==；原平衡因子的绝对值为1

• 判断类型：与孩子结点平衡因子符号：

  • 相同：LL（右旋）、RR（左旋）
  • 相反：LR、RL

8.4.2 调整最小不平衡子树A

目标：【1】恢复平衡；【2】保持二叉排序树的特性（即左子树结点值<根结点值<右子树结点值）。

平衡因子小的往左旋，大的往右旋。

• LL插入：右旋

• RR插入：左旋

• LR插入：先左旋再右旋

• RL插入：先右旋后左旋

每插入一个结点至多调整一次,全树都能达到平衡。

8.4.3 查找效率分析

在平衡二叉树中，树上任一结点的左子树和右子树的高度之差不超过1，假设以$n_{h}$表示深度为h的平衡树中含有的最少结点数，则有$n_{0}=0,n_{1}=1,n_{2}=2$，且有$n_{h} = n_{h - 1} + n_{h - 2} + 1$。

含有$n$个结点的平衡二叉树的最大深度为$O\left( logn \right)$，即平衡二叉树的平均查找长度为$O\left( logn \right)$。

8.5 B树

8.5.1 B树的定义和性质

B树，是m-ary search trees，要求所有叶结点都在同一层。B树用于数据组织，该树结构中，数据在同一个层次。

m阶的树有m-1个关键字；在B树中，根结点有$2$到$m$个孩子；其他内部结点（非终端结点）有$\lceil M / 2\rceil$到$M$个孩子，有$\lceil M / 2\rceil-1$到$M-1$个关键字。

注：

B+树则是一种索引树，M个关键字对应M个孩子。

B树的结点结构如下：

其中，$K_{i}(1≤i≤n)$为关键字（关键字按升序排序），指针$A_{i}(0≤i≤n)$指向子树的根结点

n	K1	K2	…	Kn
A0	A1	A2	…	An

8.5.2 B树的查找操作

与分块查找类似，是二叉排序树的扩展。

• 先让$key$与根结点中的关键字比较[可以采用折半查找]，如果$key$等于$K [i]$（$K []$为结点内的关键字数组），则查找成功。
• 若$key<K [1]$，则到$P [0]$所指示的子树中进行继续查找（对$p[]$为结点内的指针数组），这里要注意B树中每个结点的内部结构；
• 若$key> K [n]$的，则到$P [n]$所指示的子树中继续查找；
• 若$k [i] <key <k [i + 1]$，则沿着指针$p [i]$所指示的子树继续查找；
• 如果最后遇到空指针，则证明查找不成功。

8.5.3 B树结点的插入

当在树中插入结点到最左边的叶子时，发生overflow（溢出），需要分割，即：

$Left = [2,3] ,Middle = 5,Right = [6,7] $，将Left和Right分别作为叶子结点，然后将Middle加入到双亲结点的关键字中去。

在以下的情况中：

$Left = [55,66 ] ,Middle = 67 ,Right = [ 68,70 ] $，Middle加入关键字中去，发现关键字也已经满员，需要再通过Middle进行分割，如下所示：

8.5.4 B树结点的删除

Case1：要删除的键位于叶中，有以下方法来处理：

• 找同学借（左右兄弟）

删除键违反了节点应持有的最小键数的属性。在这种情况下，我们按照从左到右的顺序从紧邻的兄弟节点借用一个键。首先，去拜访他的左侧兄弟节点。如果左侧同级节点的键数超过最小值，则从该节点借用键。否则，尝试从紧邻的右侧同级节点借用。

• 拼桌（Merge）：如果两个直接同级节点的键数都已达到最小值，则将该节点与左侧同级节点或右侧同级节点合并，这个合并是通过父节点完成的。

如删除7结点，进行以下操作：

Case2：要删除的键位于内部节点中，有以下方法来处理：

• 如果左子节点的键数超过最小值，则删除的内部节点将替换为中序前置节点。

同理，如果右子节点的键数超过最小值，则删除的内部节点将替换为中序后置节点。

• 如果任一子级的键数正好是最小的，则合并左子级和右子级。

Case3：要删除的键位于内部节点中，并且删除该键会导致节点中的键数量减少（即少于所需的最小值）：

​ 在这种情况下，树的高度会缩小。如果目标键位于内部节点中，则查找中序前置和中序后置。如果两个子项都包含最少数量的键，则不能进行借用，可以合并孩子。

8.6 哈希表

前面所介绍的查找算法都是关键字间的比较，即基于比较的查找；哈希表则是一种基于位置的查找。

哈希表的装载密度由$\alpha = \frac{n}{sb}$来衡量，其中s是slot（槽）的大小，b是bucket（桶）的个数，$sb$指表的大小。工程上，装载密度介于0.6至0.995之间是合适的。

注：

• Hashtable由多个Bucket组成,Bucket以HashKey值为索引,每个Bucket中存放着所有HashKey相同的(Key, Value) 。在这里，我们讨论的每个Bucket的元素个数一般指1个。
• 散列的基本思想就是映射，散列表（哈希表）数据项的存储方式尤其有利于将来快速的查找定位。

对于两个标识符i,j，若$f(i) = f(j)$，则称i和j是同义词，该现象称为冲突（Collision）。

在哈希表中需要解决的两个关键问题是：

• 映射（构造Hash函数），如线性（还需要考虑时间开销）
• 解决冲突

8.6.1 哈希表的构造方法

直接定址法——适合数据的线性排列。

• 构造：取关键字或关键字的某个线性函数作哈希地址，即$H(key)=key$ 或$H(key)=a·key+b$。

• 特点：

  • 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突

  • 实际中能用这种哈希函数的情况很少

平方取中法：

• 构造：取关键字平方后中间几位作哈希地址
• 适于不知道全部关键字情况

==除留余数法==：

取关键字被某个不超过哈希表表长B的最大素数M除后所得余数，得到哈希地址，即$H(key)=key; mod; M$。

例如，当B=15时，M=13。

当关键字是小数时，可以采用以下策略：

• 放大（变成整数）
• 作乘法，并取整数部分

==折叠法==：

类似有损压缩（512—>64）。

• 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址
• 种类：
  • 移位叠加：将分割后的几部分低位对齐相加
  • 间界叠加：从一端沿分割界来回折送，然后对齐相加

数字分析法：

• 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址
• 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况

[例]有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。

随机数法：

• 构造：取关键字的随机函数值作哈希地址，即$H(key)=random(key)$。必须要注意的是，这里的随机数必须是伪随机数，即同一个数经过f运算必须保持不变。
• 适于关键字长度不等的情况

选取哈希函数，考虑以下因素：

• 计算哈希函数所需时间
• 关键字长度
• 哈希表长度（哈希地址范围）
• 关键字分布情况
• 记录的查找频率

8.6.2 处理冲突的方法

存在开散列法和闭散列法两种方法，开散列使用链式结构，闭散列使用静态存储方式（数组、顺序表等）。

8.6.2.1 开放定址法

原理：闭散列中，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

方法：当冲突发生时，形成一个探查(probe)序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即$H_{i}=(H(key)+d_{i}); mod; m,i=1,2,……k(k\leq m-1)$。

其中：H(key)表示哈希函数，m表示哈希表表长，$d_{i}$表示增量序列。

分类：

• 线性探测再散列：$d_{i}=1,2,3,…,m-1$，依次往后搜索，需构成循环形式的表
• 二次探测再散列：$d_{i}=1^{2},-1^{2},2^{2},-2^{2},3^{2},…,±k^{2}(k\leq m/2)$，右边+左边，并进行平方
• 伪随机探测再散列：$d_{i}=$伪随机数序列

注：

• $d_{i}$都是在原先位置上加上增量，m最好为素数（因为要取mod）。
• 大多数对线性探测性能的分析都假设生成的哈希值是均匀分布的，而使用线性探测，散列到已占用单元的键倾向于聚集成已占用单元的块，如当表中$i,i+1,i+2$位置上以及填有记录时，下一个哈希地址为$i,i+1,i+2,i+3$的记录都将填入$i+3$的位置，使得在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象，称为”二次聚集”。改进的方案应该分散冲突。
• 不可直接删除关键字，否则会使得其他关键字无法找到，正确的方法应为作标记，表明其进入删除状态。
• 插入时，遇到空位置或有删除标记的位置就可以插入。

[例]表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11，现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中。

(1)(蓝) 查找的比较次数为4次

​ H(38)=38 MOD 11=5 冲突
​ H1=(5+1) MOD 11=6 冲突
​ H2=(5+2) MOD 11=7 冲突
​ H3=(5+3) MOD 11=8 不冲突

(2)(灰) 查找的比较次数为3次

​ H(38)=38 MOD 11=5 冲突
​ H1=(5+1²) MOD 11=6 冲突
​ H2=(5-1²) MOD 11=4 不冲突

(3)(红) 查找的比较次数为2次

​ H(38)=38 MOD 11=5 冲突
​ 设伪随机数序列为9，则：H1=(5+9) MOD 11=3 不冲突

8.6.2.2 再哈希法

再哈希法（双哈希法）的原理是：发生冲突时，再定义一个哈希函数，并重新计算散列地址。第二个哈希函数的构造方法可以是除留余数法，或$prime-(key; %; prime)$的方法（其中素数为不超过表长的最大素数）。

双重散列探测序列是：$H_{i}=(H_{1}(key)+iH_{2}(key)); mod; m$，其中$i=1,2,…,k$。

8.6.2.3 链地址法

也称独立链表法或拉链法，该方法不会出现聚集现象。方法的原理是：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。

哈希查找过程分析：

在哈希表上进行查找的过程与哈希造表的过程基本一致。若查找不成功，会根据造表时设定的处理冲突的方法找下一个哈希地址，直到哈希表中某个位置为空（查找失败）或表中所填记录的关键字等于给定值（查找成功）为止。

8.6.3 哈希表的查找

​ 哈希查找过程仍是一个给定值与关键字进行比较的过程，评价哈希查找效率仍要用ASL。计算ASL查找成功的结果时，按照关键字进行计算；查找失败的结果则根据哈希表每个位置进行计算。哈希查找过程与给定值进行比较的关键字的个数取决于：

• 哈希函数
• 处理冲突的方法
• 哈希表的填满因子$\alpha$=表中填入的记录数/哈希表长度

[例]已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等。

查找失败的ASL根据位置进行计算，即$ASL_{nsucc}=\frac{1}{16}(1+13+12+…+2+1+1+1)$，方法是线性往后查找，发现某个位置为空时判定为查找失败。

可证明线性探测再散列的哈希表查找成功时的平均查找长度为$\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)$（通过装填因子可以间接知道散列表的大小）。

ch9.排序

9.1 排序概述

​ 排序的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。排序的空间性能基本相同，在排序算法中主要关注时间性能。

​ 排序基本操作是：

• 比较两个关键字大小：#(number) of key comparisons
• 将记录从一个位置移动到另一个位置：# of interchanges（要发生三次移动）

​ 由于待排序的记录序列中可能存在两个或两个以上关键字相等的记录，若在排序后，相对位置保持不变，则称所用的排序方法是稳定的；若相对位置发生改变，则称所用的排序方法是不稳定的。

9.2 排序的分类

按待排序记录所在位置：

• 内部排序：待排序记录存放在内存（本章描述的排序算法）
• 外部排序：排序过程中需对外存进行访问的排序

按排序依据原则：（前四个基于比较，过程可用二叉树进行表示）

• 插入排序：直接插入排序、折半插入排序、希尔排序
• 交换排序：冒泡排序、快速排序【序列中两个元素关键字比较的结果】
• 选择排序：简单选择排序（$O(n^{2})$）、堆排序
• 归并排序：2-路归并排序（分成2个子区）
• 基数排序

按排序所需工作量：

• 简单的排序方法：$T(n)=O(n^{2})$
• 先进的排序方法：$T(n)=O(nlogn)$
• 基数排序：$T(n)=O(d*n)$

这里都描述的是通过值进行排序，还有通过关系/序进行排序，即前面提到的图的拓扑排序（Topological Sort）。

9.3 排序简析

选择排序：每次将未排序序列中选出一个值放在前面，$O(n^{2})$，是不稳定的($O(n^{2})$仅选择排序不稳定)；

[优化]堆排序：堆的定义：小根堆$k_{i}\leq k_{2i}$(左子树)且$k_{i}\leq k_{2i+1}$(右子树)，自堆顶到叶子的调整过程称为“筛选”

插入排序：分为直接插入排序($O(n^{2})$，稳定，若原本有序，O(n))和折半插入排序(折半查找+插入,low>high,[low,i-1]内元素全部右移，并将A[0]复制到low所指位置)

[优化]希尔排序：分割成若干子序列，分别进行直接插入排序。L[i,i+d,i+2d,...,i+kd]，缩小增量d，重复进行以下过程。不稳定

冒泡排序：$O(n^{2})$，稳定

[优化]快速排序：首元素作为基准元素，low、high指针，比基准元素小的放low左，大的放high右，当low==high时即为基准元素所放位置，然后对两个子序列递归进行快速排序，O(nlogn)，不稳定

归并排序：O(nlogn)，稳定

基数排序：对于整数的排序，先按照个位数从小到大的顺序排放元素，得到新顺序的序列，再按照十位数从小到大的顺序在上一步的新顺序中再次排放元素，再按照百位数从小到大的顺序在上一步的新序列中再次排放元素。稳定

注：

快速排序与归并排序详细笔记见：算法1:基础算法

*双向冒泡：

typedef struct {
	char key;
}Type;
//双向冒泡排序
void BidirectionalBubbleSort(Type r[], int n, int CompareCount, int MoveCount) {

	int front, behind;
	int flag;
	Type temp;
	front = 0;
	behind = n - 1;
	while (front < behind) {
		flag = 0;
		for (int i = front; i < behind; i++) {//正向冒泡,从前面第一个开始往后走
			CompareCount++;
			if (r[i].key > r[i + 1].key) {//把大的数往后推
				temp = r[i];
				r[i]= r[i + 1];
				r[i + 1]= temp;
				flag = 1;//标志有数据交换
			}
		}
		if (!flag)//若flag还是等于0，即表明没有进行交换，就是说已经有无需进行下一步了序的
			break;
		behind--;
		for (int i = behind; i > front; i--) {//反向冒泡，从最后一个开始往前走
			CompareCount++;
			if (r[i].key < r[i - 1].key) {//找到剩下中最小的，把小的数往前推
				temp = r[i];
				r[i] = r[i - 1];
				r[i - 1] = temp;
			}
		}
		front++;
		MoveCount++;
		printf("第%.2d趟排序的结果：", MoveCount);
		for (int k = 0; k < n; k++) {
			printf("%d ", r[k].key);//输出排序每一步的过程
		}
		printf("\n");
	}
	printf("比较次数为：%d\n", CompareCount);//比较次数
	printf("移动次数为：%d\n", MoveCount);//移动次数
}