C语言——排序（插入、交换、选择、归并、基数排序）_交换插入方法

前言

《数据结构最后一弹》——排序
看完本篇，你将了解：
①查找问题概述，二者的联系
②插入排序（直接插入排序、折半插入排序、2–路插入排序、表插入排序、希尔排序）
③交换排序（冒泡排序、快速排序）
④选择排序（简单选择排序、堆排序）
⑤归并排序
⑥基数排序（多关键字排序介绍）

一、查找问题概述

1.基本概念

（1）“排序”是基于数据逻辑结构T=(D,R)定义的一种重要的运算。
（2）功能是将一个数据元素的任意序列，依据关键字的大小，重新排列成一个有序的序列。
（3）D是数据元素集;
	R是数据元素之间关系偶对集。
（4）为何要排序呢？
 		例子:由多个数据元素构成的序列中查找关键字等于某个具体值的数据元素。
		讨论:如果数据元素元素的关键字无序的话，我们只能采用顺序查找方法，代价高。
		反之，如果数据元素元素的关键字有序的话，则可以采用如折半查找的更高效率的查找方法。
（5）术语:能唯一标识数据元素的一个分量或多个分量的组合称为关键字;
 不能唯一标识数据元素的分量称为次关键字。
注：如果一个排序的算法，对于数据元素按照次关键字排序后，能确保相同次关键字的数据元素排序前后，相对次序不变，则称该算法称为是稳定的，否则称该算法是不稳定的。
（6）内部排序：指对存储在计算机的主存储器（也称“内存”）中的数据进行排序的过程。
（7）外部排序：指对存储在计算机的外存储器（也称“外存”）中的数据进行排序的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13

注：在此我们只讨论内部排序

2.内部排序

（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序

二、插入排序

1.直接插入排序法

（1）基本原理：先把a1看成一个有序的包含一个数据元素的序列。然后不断地在一个递增有序的序列(a1,…,ai-1)(2≤i≤n)中，插入一个数据元素a，使得a1,…ai-1，ai构成一个新的有序的序列。
（2）基本步骤
①确定插入位置;
②移动元素;
③填入新元素。
也可合并为 ①边确定插入位置边移动元素;
②填入新元素。

（3）正序情况：算法的比较次数和移动次数均达到最好，待插入元素仅仅与左边一个元素比较一次，不需要移动。
即：比较次数和移动次数分别为n-1次和0次
（4）逆序情况：算法的比较次数和移动次数均达到最坏
即:比较和移动次数分别为2+3+…+n次和(2+1)+(3+1)+…+(n+1)次。
（5）算法时间性能:Tbest(n)=O(n)，Tworst(n)=O(n^2)
假设待排序的数据元素的各种排列概率相同，可以取上述最小值和最大值的均值作为算法的比较平均次数和移动平均次数，约为n^2/4次。
Taverage(n)= O(n^2)
（5）变种：
①半插入排序
②2-路插入排序
③表插入排序
④希尔排序

2.折半插入排序

（1）折半插入排序是利用待插入表的有序性，将上述直接插入排序中的顺序查找定位，改进采用为折半查找法定位。
（2）最坏情况降至O(nlog n)，总移动元素次数不变，故算法最坏和最好时间复杂度不变
Tworst(n)=Taverage(n)= o(n^2)

3.2-路插入排序

（1）利用辅助数组的存储空间，首尾视为循环状态，以D[1]作为中间位置分为两个有序子表
将待排序的数据元素，分情况选择插入到这两个子表的某一表中

（2）算法思想：
①取出表L=(a, a2, a3,… , aj, … , an )的第1个元素a存入辅助空间D[1];
②取出表L的下一个元素ai(2≤i≤n)，如果ai<D[1]，则插入到D[1]之左边的有序子表，否则插入到D[1]之右边的有序子表;
③重复②，直到表L的最后一个元素an插入后为止
（3）算法时间性能：确定插入位置的最坏情况和平均情况的移动次数可减少大约一半
但比较次数不变，故算法最坏和最好时间复杂度不变
Tworst(n)=Taverage(n)= o(n^2)

4.表插入排序

（1）定义：表插入排序是基于静态链表的这样一种物理存贮结构，将待排序数据元素按照大小顺序建立起静态链表。
这个静态链表是以0下标为头结点的循环链表，头结点存储关键字的最大理论值MAXINT,担当“哨兵”作用。
（2）算法思想：
从表L=(a1,a2,a3,… , ai… , an)的第2个元素a2开始，直到最后一个元素an为止，逐个插入ai到以0下标为头结点的循环静态链表，使其仍然保持有序。
（3）插入每个元素ai的操作：
①确定插入位置，即从循环静态链表首结点开始，第一次遇到大于ai的元素x时，x所在结点之前为ai元素所在结点的插入位置;
②修改指针，即ai元素所在结点指向x所在结点，将x所在结点的前驱结点指向ai元素所在结点。
（4）算法时间性能：需要n-1趟插入，仅需2n次指针修改，避免数据元素移动的运算
比较次数与直接插入一样，故算法最坏和最好时间复杂度不变
Tworst(n)=Taverage(n)= o(n^2)

5.希尔排序

（1）直接插入排序的特性：待排序数据元素序列越接近正序，其时间复杂度会越低。
待排序数据元素序列为正序时，其时间复杂度会从O(n^2)逐渐降低至O(n)。
（2）基本思想：利用上述特性
先将整个待排序数据元素序列分割成若干个子序列分别进行直接插入排序，待整个序列中的数据元素“基本有序”时，
再对全体数据元素构成的序列进行一次直接插入排序。
（3）把在第i步中，整个序列分成的组数记为di。一共进行的排序趟数计做m。那么，这里应该满足如下一些条件:
①dm=1：最后总要进行一次直接插入排序
②当1<=i,j<=m，且 i<j时，di>dj
③当1<=i,j<=m，且i不等于j时，di和dj的最大公约数为1
（4）算法时间性能：时间开销与每一趟分组过程相关，准确的时间复杂度到目前为止尚无定论

三、交换排序法

1.基本原理

通过不断进行两个元素之间位置的交换，逐步使得每个数据元素移动到表L的正确位置，最后得到一个有序序列。
应用上述原理的排序：冒泡排序、快速排序

2.冒泡排序

（1）原理：按照从左至右的顺序，从左边的第一个元素开始，依次比较相邻位置的两个数据元素，
如果逆序则交换它们的位置。这样进行一趟比较交换，可以将最大值交换到最后的位置即正确位置。
第一趟:对于表L-(ai, az, a3,… , ai，… , an )，从左至右的顺序，将序号相邻的、反序的两个元素交换。
第一趟结束后，an就是关键字最大的那个数据元素;
第二趟:对于除最后一个数据元素之外的剩余部分构成的子表重复第一步，第二趟结束后，
an就是关键字次大的那个数据元素;以此类推。直到剩余部分构成的子表表长等于1为止。
（2）举例：

（3）分析：假设表中数据元素为n个，即问题规模为n，统计关键字比较和元素交换这两个主要运算的实际执行次数。
冒泡排序需要n-1趟，第i趟(i:1到n-1)需要n-i次比较运算，最多需要n-i次交换运算，最少需要0次交换运算。
算法的比较次数总是(n-1)+(n-2)+…+(1)次。
在“正序情况”之下，算法的交换次数达到最好，不需要移动。即0次。
在“逆序情况”之下，算法的交换次数达到最坏，移动次数为(n-1)+(n-2)+…+(1)次。
（4）算法时间性能：Tbest(n)= O(n^{2)，Tworst(n)=O(n}2)。

3.快速排序

（1）原理：快速排序是通过一趟交换，将待排序序列的第1个数据元素交换到正确位置。

（2）基本思想：
①依据表L=(a1, a2, a3,… , ai, … , an)的第一个元素ai，把an放在合适的位置，
以将表L“划分”成左右2个逻辑子表，使得ai大于左子表的所有元素，且小于右子表的所有元素
②左、右子表分别递归处理。
（3）算法核心：做划分处理
（4）划分方法：
首先low和high初始值分别指向表L的最左和最右的单元。
①当low<high时， 重复做如下处理:
(1.1)向左移动high,将首次遇到的小于L[low ]的L[high]与L[low]交换;
(1.2)向右移动low,将首次遇到的大于L[high]的L[ow]与L[high]交换。
（5）举例

high向左找到第一个小于49的元素27，此时high=7，将27,49交换

low向右一个单元，并从此开始向右找到一个大于49的元素65，此时low=3，将65,49交换
high向左移动一个，继续找，依次类推
结束后，

a1=49所在的位置4就是其正确的位置，划分出左边[1-3]和右边[5~8]待排序的两个子表。
（6）算法时间性能：假设表中数据元素为n个，即问题规模为n，统计关键字比较和元素交换这两个主要运算的实际执行次数。
对于n个数据元素“划分”，需要n-1次比较，元素交换次数最少0次，最多n-1次。
（7）分析：对于n个数据元素快速排序，其过程可以用一颗二叉树表示，
即树根是待划分的第一个数据元素，其左子树是“划分”后的第一个数据元素所在位置的左部所有元素，右子树是“划分”后的第一个数据元素所在位置的右部所有元素。

①二叉树的每层划分需要的比较次数和交换次数不超过O(n)。
而二叉树的层数即高度取决于待排序数据元素的初始序列情况，在每次划分都出现左部和右部之一没有数据元素情况下，
②例如初始序列为有序的情况，二叉树的层数即高度达到最大为n;在每次划分均出现左部和右的数据元素个数相等情况下，二叉树的层数即高度达到最小为clogn。
总结：快速排序时间效率由“二叉树的每层划分需要的比较次数和交换次数”ד二叉树的层数即高度”确定。
Tbest(n)=O(nlogn)，Tworst(n)=O(n^2)。
假设n个元素的平均比较次数为Ta(n)，划分后左子表元素个数为i，并且i取(0到n-1)是等概率的，则

四、选择排序

1.基本原理

先选择表L的最大元素，与最后位置上元素交换;然后选择表L的次大元素，
与倒数第二个位置上元素交换;依次类推，最后得到一个有序的序列。

2.常见算法

（1）简单选择排序
（2）堆排序

3.简单选择排序

（1）概念：简单选择排序是采用顺序查找法确定最大元素的位置，与最后位置上元素交换。
（2）算法思想：
①对于表L=(a , a2,a3,… , aj, … , an)，顺序遍历，选择出最大元素所在位置，与最后位置元素交换;
②对于除最后一个元素之外的剩余部分构成的子表重复①，直到剩余部分构成的子表表长等于1为止。
（3）算法时间性能
假设表中数据元素为n个，即问题规模为n，统计关键字比较和元素交换这两个主要操作的实际执行次数。
对于由n个数据元素构成待排序序列，需要n-1趟选择。、
第i趟(i取值从1到n-1)需要n-i次比较运算，最多需要1次交换运算，最少需要O次交换运算。
Tw(n)=Tb(n)-(n-1)+(n-2)+…+(1)=O(n^2)= Ta(n)

4.堆排序

（1）概念：堆排序是利用构建“堆”的方法确定具有最大值的数据元素，并把该元素与最后位置上元素交换。
（2）堆：满足下列条件的n个数据元素序列(a1 ,a2,…,an）称为堆。
ai>=a2i
ai>=a2i+1(1≤i≤n/2)
可以将任意一个由n个数据元素构成的序列(a1 ,a2 ,…,an)，
按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树。
（3）举例：

（4）结论：根结点值应当最大
（5）堆和堆排序算法思路：堆排序的思路是将表L=(a1,a2, a3 ,… , aj, … , an)转换成大顶堆，
将堆的根（即L第一个位置的元素)与最后一个叶子(即L最后一个位置的元素)交换;
然后，除最后一个叶子外剩余部分再重复上述处理。
构建堆的过程即为找最大元素的过程，是堆排序的关键
（6）调整堆：假设表L=(a1 , a2 , a3,… , ai,… , an)对应的完全二叉树T中，树根的右子树均为堆，
仅仅是T的根不满足堆的条件。将这种特殊情况的完全二叉树T转换成堆的过程，称为“调整堆”。
（7）调整堆基本思想：
①将树根与其左右子树根值最大者交换;
②对交换后的左(或右)子树重复①，直到左(或右)子树为堆。
举例：

根38不满足堆的条件，交换38与左子树根值97

交换后根38仍不满足堆的条件，交换38与左子树根值76，

以此类推，

调整堆完成
（8）调整堆算法：

//调整堆的算法：
typedef SqList HeapType;//采用顺序表存储
void HeapAdjust(HeapType &H,int s,int m)//除了H.rs[s].key之外，H.r[s...m]的关键字均满足堆的定义
//本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大顶堆 
{
	rc=H.r[s];
	for(int j=2*s;j<=m;j*=2)//沿可以较大的孩子结点向下筛选
	{
		if(j<m&&LT(H.r[j].key,H.r[j+1].key))
			++j;//j为key较大的记录下标
		if(!LT(rc.r[j].key,H.r[j].key))//rc应插入在位置s上 
			break; 
	}
	H.r[s]=rc; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（9）创建堆算法思想：从最大序号的非叶子结点开始逐步到根，对于每棵子树，调用“调整堆”算法，使其成堆。
（10）堆排序算法思想：
①创建堆:从最后一个非叶子结点开始逐步到树根，对于每个子树进行调整堆;
②重复n-1 次如下处理:将堆的根与最后一个叶子交换;除最后一个叶子之外剩余部分再调整堆。
（11）堆排序算法：

//堆排序的算法：
void HeapSort(HeapType &H)//采用顺序表存储，进行堆排序
{
	for(int i=H.length/2;i>0;--i)
	{
		HeapAdjust(H,i,H.length);//将H.r[1..H.length]建成一个大顶堆 
	}
	for(int i=H.length;i>1;--i)
	{
		//交换H.r[1]和H.r[i],将堆顶记录与当前未排序子序列的最后一个记录交换
		HeapAdjust(H,i,i-1);//将H.r[1..i-1]重新调整为一个大顶堆 
	}
}  


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（12）堆排序算法分析： 假设表中数据元素为n个，即问题规模为n，
统计关键字比较和元素交换这两个主要操作的实际执行次数。
①“创建堆”，从最后一个非叶子结点开始直到树根进行n/2次调整，其总共比较的次数≤4n。
②“n-1次调整”，其总共比较的次数2(log(n- 1)+ log(n-2)…+log(2))≤2nlogn 。
交换操作的次数不超过比较操作的次数，所以堆排序算法的最坏时间复杂度为O(n lgn),
即:Tworst(n)= O(nlogn)。

五、归并排序

1.基本原理

两个有序表合并(merge)成为一个有序表。

2.算法思想 （可递归或非递归）
对线性表L=(a1,a2,a3…,ai…,an)的每个元素，看成一个有序子表
（1）从左至右，将相邻的两个有序子表合并之;
（2）重复（1），直到所有子表合并成一个有序子表为止。
举例：

3.算法分析：（比较次数）
假设表中数据元素为n个，即问题规模为n，统计关键字比较和元素移动的实际执行次数。
对于归并算法，假定两个有序表的数据元素总个数为n，则将两个有序表合并成为一个有序表的比较次数最多为n-1次。
注：可用一颗二叉树表示，如刚刚的例子

树中一个结点对应于一个有序表，一个父节点有两个子节点，表示对应于两个子节点的有序表，归并得到一个对应于父节点的有序表。
对于任意n个数据元素构成的待排序序列，也可以用这样一棵二叉树表示。
每一趟合并比较次数≤n-1，二叉树的高度≤clogn (c为常数)。
最坏时间复杂度:Tworst(n)= O(nlogn)
但需要额外使用n个存储单元空间 ：空间复杂度:S(n)= O(n)

六、基数排序

——不依赖于关键字之间的比较运算，且借助多关键字排序的思想对单逻辑关键字排序

1.多关键字排序

（1）概述：假设有n个数据元素的序列{R1,R2,…，Rn}且每个数据元素Ri中含有d个关键字(K0,K1,…,Kd-1)。
其中，k0称为最主位关键字，kd-1称为最次位关键字
（2）分类：多关键字排序可以分为最主位优先排序和最次位优先排序两种。

（3）最主位优先排序 (MSD - Most Significant Digit first)
①算法思想：
1）首先将所有的数据元素按照最主位，也就是第1个关键字K0进行排序，将序列分成若干子序列，每个子序列中的数据元素都具有相同的K0值;
2）之后，对于具有相同K0值的子序列，再依据第2个关键字K1分别排序;
3）依此类推，直到对相应子序列分别依据第d个关键字Kd-1排序为止，将所有子序列链接在一起构成整个有序序列。

②举例：待排序的双关键字序列

（4）最次位优先排序(LSD - Least Significant Digit first)
①算法思想：
1）首先依据最次位关键字，也就是第d个关键字Kd-1排序;
2）之后，对于整个序列，再依据第d-1个关键字Kd-2排序;
3）依此类推,直到对整个序列依据第1个关键字K0排序为止。此时得到整个有序序列。
②举例：待排序的双关键字序列

（5）MSD和LSD排序方法的不同特点总结:
①若按照MSD进行排序，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序;
②若按照LSD进行排序，不必分割成子序列，对每个子序列都是整个序列参加排序，且只能用稳定的排序方法。

2.基数排序

——假设关键字一共有n位。
（1）基本原理：
将关键字每一位Km视为一单关键字，这样排序问题就转换成多关键字(K1，K2，K3,…， Kn-1)排序，
并采用最次位优先排序方法，即LSD方法进行排序。
（2）举例：278 109 063 930 589 184 505 269 008 083
关键字是三位的十进制数，(需要3趟进桶和出桶操作)

1）第一趟:从左到右，依次将关键字序列中的每个关键字按照最低位进入对应编号的“桶”;
之后，从0号到9号的顺序将关键字移回原来的存储区。

			入桶完毕，从0开始出桶 
			![在这里插入图片描述](https://img-blog.csdnimg.cn/20210713165039587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMzA4Mzcz,size_16,color_FFFFFF,t_70#pic_center)
1
2

2）第二趟:从左到右，依次将关键字序列中的每个关键字按照次低位进入对应编号的“桶”
之后，从0号到9号的顺序将关键字移回原来的存储区。

入桶完毕，从0开始出桶

3）第三趟:从左到右，依次将关键字序列中的每个关键字按照百位进入对应编号的“桶”
之后，从O号到9号的顺序将关键字移回原来的存储区。

入桶完毕，从0开始出桶

总结：可以看出，工作区（“桶”）满足先进先出的特性，逻辑上是一个队列。
（3）假设每个关键字的每一位可能的取值的情形数目为r，把它定义为基数。
（如刚刚例子中r=10）
①首先，开辟一块连续的地址空间，作为存贮区，存放待排序的关键字序列;
②然后，从最低位开始直到最高位，将存储区的关键字依次进行“入桶”操作，然后依次进行“出桶”操作，存放到存储区中。
③之后，入桶和出桶操作重复d遍(d代表关键字中的位数)。
（4）时间性能
假设表中数据元素为n个，即问题规模为n，关键字的基数r，每个关键字有d位。
若桶采用顺序存储结构，移动元素操作（出入桶）即为主要操作
①基数排序一共需要进行d趟，每趟每个关键字需要2次移动（对应于入桶和出桶)，每趟合计移动2n次。
基数排序共计移动2nd次，即:T(n,d)-o(d·n)。
②需要额外的r n个存储空间，即:S(n,r)=O(r·n) 。

总结

本篇是数据结构的最后一篇，重点在于讲解原理，所以除了堆排附了一些伪码之外，其他排序都是贴图讲解的。
可自取哦~
（下一篇估计要咕咕好久了）