典型排序的C语言实现及其思路解析

1. 基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】：

初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 3.

void selectionSort(Type* arr,long len) {

long i=0,j=0;/*iterator value*/ long maxPos;

assertF(arr!=NULL,\ for(i=len-1;i>=1;i--) {

maxPos=i; for(j=0;j

if(arr[maxPos]

选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换. 二.直接插入排序

插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 直接插入排序

直接插入排序（Straight Insertion Sort）：将一个记录插入到排好序的有序表中，从而得到一个新的、记录数增1的有序表。 直接插入排序算法

哨兵（监视哨）有两个作用：一是作为临变量存放R[i]（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。

当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。

直接插入排序是稳定的排序方法。 三. 冒泡排序

[算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上\飘浮\。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

[算法]：

void BubbleSort(SeqList R) {

//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j；

Boolean exchange； //交换标志

for(i=1;i

exchange=FALSE； //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key

R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]； R[j]=R[0]；

exchange=TRUE； //发生了交换，故将交换标志置为真 }

if(!exchange) return；//本趟排序未发生交换，提前终止算法 } //endfor(外循环) } //BubbleSort

[分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 [算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上\飘浮\。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

[算法]：

void BubbleSort(SeqList R) {

//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j；

Boolean exchange； //交换标志

for(i=1;i

exchange=FALSE； //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key

R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]； R[j]=R[0]；

exchange=TRUE； //发生了交换，故将交换标志置为真 }

if(!exchange) return；//本趟排序未发生交换，提前终止算法 } //endfor(外循环) } //BubbleSort

[分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 四. 希尔排序 基本思想：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2

该方法实质上是一种分组插入方法。 给定实例的shell排序的排序过程

假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1 Shell排序的算法实现

1． 不设监视哨的算法描述 void ShellPass(SeqList R，int d)

{//希尔排序中的一趟排序，d为当前增量 for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区 if(R[i].key

R[0]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵 do {//查找R[i]的插入位置

R[j+d]；=R[j]； //后移记录 j=j-d； //查找前一记录

}while(j>0&&R[0].key

R[j+d]=R[0]； //插入R[i]到正确的位置上 } //endif } //ShellPass

void ShellSort(SeqList R) {

int increment=n； //增量初值，不妨设n>0 do {

increment=increment/3+1； //求下一增量

ShellPass(R，increment)； //一趟增量为increment的Shell插入排序 }while(increment>1)

} //ShellSort 注意：

当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件\，以防下标越界。 2．设监视哨的shell排序算法 算法分析

1．增量序列的选择

Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： ① 最后一个增量必须为1； ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

2．Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因： ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 3．稳定性

希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。 五. 堆排序

1、 堆排序定义

n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。 2、大根堆和小根堆

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 3、堆排序特点

堆排序(HeapSort)是一树形选择排序。

堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，

利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。 4、堆排序与直接插入排序的区别

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

5、堆排序

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 （1）用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 ……

直到无序区只有一个元素为止。 （2）大根堆排序算法的基本操作： ① 初始化操作：将R[1..n]构造为初始堆； ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。 注意： ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。 （3）堆排序的算法： void HeapSort(SeqIAst R)

{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int i；

BuildHeap(R)； //将R[1-n]建成初始堆

for(i=n;i>1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换

Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort

（4） BuildHeap和Heapify函数的实现

因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。 ① Heapify函数思想方法

本文来源：https://www.bwwdw.com/article/fwk2.html