[数据结构与算法]C语言实现排序算法

前言

对于排序而言，在生活中经常会遇到，比如学校考试成绩的排序，而对于排序也存在着其稳定性，像当学校有两个同学a和b的成绩相同的时候，我们通过学号(下标)进行排序，在学号前面的a同学就会被排到第一，这种情况我们称为稳定排序，反之如果学号在前面的a同学并没有排到第一，而是b同学排到第一，那么我们称为不稳定排序。

对于排序而言我们还分为了两种形式：

• 内排序：在排序整个过程中，待排序的所有记录全部被放置在内存中
• 外排序：由于排序记录个数多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据

这里就主要了解内排序的算法性能：

1. 时间性能
2. 辅助空间
3. 算法的复杂度

排序算法有许多，这里我们就介绍一些常见的吧。

先提供一个用于排序用的顺序表结构，此结构也将用于后面要讲的所有排序算法，这里我们从小标为1的索引开始，留下下标为0的索引作哨兵或者临时变量。

#define MAXSIZE 10        // 用于要排序数组个数的最大值，可根据需要修改

typedef struct {
    int r[MAXSIZE + 1];   // 用于存储要排序数组，r[0]用作哨兵或者临时变量
    int length;           // 用于记录顺序表的长度
}SqList;
typedef  int Status;

还有一个排序常用于数据交换的函数

void swap(SqList* L, int i, int j) {  // 变换L中数组r的下标为i和j的值
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

一、冒泡排序

冒泡排序(Bubble Sort)一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。

void BulleSort(SqList *L) {
    int i, j;
    Status flag = 1;                           // flag 用来作为标记
    for (i = 1; i < L->length && flag; i ++) {  // 若flag为true则对出循环
        flag = 0;                           // 初始为flase
        for (j = L->length - 1; j >= i; j --) {
            if (L->r[j] > L->r[j + 1]) {
                swap(L, j, j+1);                  // 交换 L->r[j]于 L->r[j + 1]的值
                flag = 1;                    // 如果有数据交换，则flag为true
            }
        }
    }
}

用标记变量flag来记录数据是否还需要进行两两交换，如果为FALSE则此序列已经有序了。

冒泡排序的时间复杂度为O(n2)

二、选择排序

简单选择排序法(Simple Selection Sort)就是通过n-i此关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换。

void SelectSort(SqList* L) {
    int i, j,min;                        
    for (i = 1; i < L->length; i++) {
        // 最小索引
        min = i;
        for (j = i + 1; j <= L->length; j++) {
            if (L->r[min] > L->r[j]) {
                min = j;
            }
        }
        if (i != min) {
            swap(L, i, min);
        }
    }
}

选择排序的时间复杂度为O(n2)

三、直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表，类似于当前面索引数据大于后面一位的时候，则会进行排序操作，前面会设置哨兵(索引为0的那一个参数)，并且会将后面一位的值依次向前查找大于哨兵则后移一位，直到数据小于为止，之后再将哨兵(记录了当前小于前一位索引的值)插入回正确的位置。

void InsertSort(SqList* L) {
    int i, j;
    for (i = 2; i < L->length; i++) {
        if (L->r[i] < L->r[i - 1]) {
            L->r[0] = L->r[i]; // 哨兵
            for (j = i - 1; L->r[j] > L->r[0]; j--) {
                // 如果前面的值大于哨兵的值,那们让该值后移,覆盖掉大于的值，继续执行
                L->r[j + 1] = L->r[j];
            }
        	// 排序过后自己的位置
            L->r[j + 1] = L->r[0];
        }
    }
}

直接插入排序的时间复杂度在最好的情况下为O(n)，最坏的情况为O(n2),所以在性能上比冒泡和简单选择排序要好一些。

四、希尔排序

对于上面各种排序算法的时间复杂度基本上都是O(n2)，当很多人都以为这是极限的时候，突然出现了一个科学家改变了思维的方式，通过换位思考计算出了比O(n2)小的算法，而那位科学家就是希尔。

而他的算法思想其实为，将一个数组分成了三组，分别为上、中、下三部分组成，从小到大排序，最后在将这3组数据拼合起来就完成了排序方法，但是对于无序的数据而言，怎么能断定相邻的3个数据就一定在同一个部分当中呢?那么希尔排序的演变过程就诞生了，其通过一个增量的形式来记录两个值的间距，直到增量<=1为止完毕。

void ShellSort(SqList *L)
 {
     int i,j;
     int increment=L->length;
     do
     {
         increment=increment/3+1;            /* 增量序列 */
         for(i=increment+1;i<=L->length;i++)
         {
             if (L->r[i]<L->r[i-increment])    /* 需将L->r[i]插入有序增量子表 */
             {
                 L->r[0]=L->r[i];             /* 暂存在L->r[0] */
                 for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
                     L->r[j+increment]=L->r[j]; /* 记录后移，查找插入位置 */
                 L->r[j+increment]=L->r[0]; /* 插入 */
             }
         }
     }
     while(increment>1);
 }

希尔排序的时间复杂度为O(n*logn)

五、堆排序

对于堆排序，在此之前我们需要先了解完全二叉树的特性。

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

而二叉树的性质是如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]。那么对于有n个结点的二叉树而言,它的i值自然就是小于等于[n/2]了，即下标i与2i(i结点的左子树)和2i+1(i结点的右子树)为双亲子女关系。

而这里我们通过大顶推的方式来实现推排序，而大顶推的类似于，根节点为最大值，每个结点的左右子树都不会大于该结点，利用这样的特性我们可以通过最大的值根节点和最后一个值替换，像叠罗汉一样，然后又通过转化为大顶推的形式将第二大的值放上来继续推出了…

而我们的大顶堆的代码该如何实现呢?这里我们通过定义HeapAdjust函数：

/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
1 void HeapAdjust(SqList *L,int s,int m)
2 { 
3  int temp,j;
4  temp=L->r[s];
5  for(j=2*s;j<=m;j*=2)  /* 沿关键字较大的孩子结点向下筛选 */
6  {
7   if(j<m && L->r[j]<L->r[j+1])
8    ++j;   /* j为关键字中较大的记录的下标 */
9   if(temp>=L->r[j])
10    break;   /* rc应插入在位置s上 */
11   L->r[s]=L->r[j];
12   s=j;
13  }
14  L->r[s]=temp;   /* 插入 */
15 }

这里就是大顶推的代码实现，而参数L就不用介绍了，参数s为当前结点序号，而m即为数组总长度，而第5行执行的循环中j的值实则为j的右子树，j+1则为左子树，然后迭代下去，第7行则是当j不是最后一个结点且当前结点的左子树<当前结点右子树的时候，让j+1(因为此时右子树>左子树所以右子树成了与当前结点比较的参数,如第9行，如果当前结点大于右子树则直接跳出),如果右子树>当前结点，那么右子树的值将在第11行替换掉当前结点，并将j(右子树的下标)赋值给s，将右子树的位置替换当前结点，然后继续进行下一个根节点左右子树最大值的寻找，如果还不明白可以自行调试。

堆排序完整代码：

/* 对顺序表L进行堆排序 */
1 void HeapSort(SqList *L)
2 {
3  int i;
4  for(i=L->length/2;i>0;i--)  /* 把L中的r构建成一个大顶堆 */
5    HeapAdjust(L,i,L->length);

6  for(i=L->length;i>1;i--)
7  { 
8    swap(L,1,i);    /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
9    HeapAdjust(L,1,i-1);   /* 将L->r[1..i-1]重新调整为大顶堆 */
10  }
11 }

这里i的值为长度/2，原因也来自于二叉树的特性，该操作会获取到所以二叉树的根结点下标，通过循环把所有值都转化为了大顶堆，然后在第6行的循环中，用叠罗汉的方式，把当前最大值与最后一个值替换，然后继续调用HeapAdjust函数又转化为大顶堆，以此类推，直到所有循环结束，排序完成。

堆排序的时间复杂度为O(n*logn)

六、归并排序

对于归并排序的理解，类似于将一个数组全部拆分出另一个数组，然后在以此数组继续拆分，直到无法拆分后，继续排序，排序完成后将排序完成的数组拼凑回来，然后将排序完成的值返回，该算法用2种实现方法，第一种则是我们最容易想到的递归实现，因为递归和归并非常相似(重复的做同样的事情，当无法拆分时为条件退出判断，在此之前调用排序方法,然后返回)，而还有一种则是通过非递归实现。

1.递归实现归并排序

/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
	int m;
	int TR2[MAXSIZE+1];
	if(s==t)
		TR1[s]=SR[s];
	else
	{
		m=(s+t)/2;				/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
		MSort(SR,TR2,s,m);		/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
		MSort(SR,TR2,m+1,t);	/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
		Merge(TR2,TR1,s,m,t);	/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
	}
}
 
/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{ 
 	MSort(L->r,L->r,1,L->length);
}
 /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
	int j,k,l;
	for(j=m+1,k=i;i<=m && j<=n;k++)	/* 将SR中记录由小到大地并入TR */
	{
		if (SR[i]<SR[j])
			TR[k]=SR[i++];
		else
			TR[k]=SR[j++];
	}
	if(i<=m)
	{
		for(l=0;l<=m-i;l++)
			TR[k+l]=SR[i+l];		/* 将剩余的SR[i..m]复制到TR */
	}
	if(j<=n)
	{
		for(l=0;l<=n-j;l++)
			TR[k+l]=SR[j+l];		/* 将剩余的SR[j..n]复制到TR */
	}
}

这里整体就是一个递归拆分、排序、重合的过程，我们这里只讲实现排序的Merge函数，该方法获取每一次通过递归一次一次拆分的数组进行排序(每执行一次该函数，会有两个拆分的数组进行排序)，并放入TR中存储着，然后两两分别进行判断，小的往前放，然后最后通过判断将归并剩下的数组移动到TR后面。

2.非递归实现归并排序

对于递归实现的方法，虽然代码容易理解，但是会造成一些时间、空间上的性能损耗。为了提高性能，我们可以通过将递归的方式改为迭代的方式，通过迭代方式修改后性能也会进一步提高。

/* 非递归法 */
 /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
	int j,k,l;
	for(j=m+1,k=i;i<=m && j<=n;k++)	/* 将SR中记录由小到大地并入TR */
	{
		if (SR[i]<SR[j])
			TR[k]=SR[i++];
		else
			TR[k]=SR[j++];
	}
	if(i<=m)
	{
		for(l=0;l<=m-i;l++)
			TR[k+l]=SR[i+l];		/* 将剩余的SR[i..m]复制到TR */
	}
	if(j<=n)
	{
		for(l=0;l<=n-j;l++)
			TR[k+l]=SR[j+l];		/* 将剩余的SR[j..n]复制到TR */
	}
}
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{
	int i=1;
	int j;
	while(i <= n-2*s+1)
	{/* 两两归并 */
		Merge(SR,TR,i,i+s-1,i+2*s-1);
		i=i+2*s;        
	}
	if(i<n-s+1) /* 归并最后两个序列 */
		Merge(SR,TR,i,i+s-1,n);
	else /* 若最后只剩下单个子序列 */
		for(j =i;j <= n;j++)
			TR[j] = SR[j];
}
 
/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
	int* TR=(int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
    int k=1;
	while(k<L->length)
	{
		MergePass(L->r,TR,k,L->length);
		k=2*k;/* 子序列长度加倍 */
		MergePass(TR,L->r,k,L->length);
		k=2*k;/* 子序列长度加倍 */       
	}

从代码中可以感受到非递归的迭代归并排序做法非常直截了当，主函数MergeSort2出发，分配空间给TR，然后从索引1开始(本章算法的索引0为临时变量)，循环条件为当k<当前数组长度，之后调用了MergePass函数，从最小的序列开始归并直至完成。不需要像递归那样先拆分递归，再归并退出，而是执行完毕后将k的值(即归并排序的范围)扩大原来的两倍，继续调用MergePass函数在将k的值加倍…

而我们MergePass函数则是将原来无序的数组两两归并入TR，其中在该函数的n-2*s+1(归并范围),而这个s即为k(也就是归并排序的范围)，而我们为什么要+1呢，其实就是因为两两归并，如果为数组长度为奇数的值，那么定会剩下来，导致无法归并。

而这个Merge函数我们之前在递归实现时讲过这里不讲了，此时的i + s - 1 和i + 2 * s - 1即让SR(即L->r)中的第一个和第二个记录归并到TR中,然后执行i=i+2*s继续下一个参数归并，直到i<归并范围为止，最后将剩下的序列归并(如果有两个则调用Merge函数进行归并，如果只剩下一个则直接插入到后面)。

归并排序的时间复杂度为O(n*logn)，所以说归并排序算一种比较占内存、但效率高且稳定的算法。

七、快速排序

那么到最后一个，快速排序，快速排序是最早由图灵奖获得者Tony Hoare设计出来的，该算法被称为20世纪十大算法之一，而每一个算法都有其演变的过程，比如我们上面讲的希尔排序相当于直接插入排序的升级，它们同属于插入排序列，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序即为我们前面认为最慢的冒泡排序的升级，它们都属于选择排序类。

而快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。

快速排序的思想非常精妙，我们从代码中解析。

1.快速排序算法

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{ 
 QSort(L,1,L->length);
}

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{ 
int pivot;
 if(low<high)
 {
  pivot=Partition(L,low,high);  /* 将L->r[low..high]一分为二，算出枢轴值pivot */
  QSort(L,low,pivot-1);   /*  对低子表递归排序 */
  QSort(L,pivot+1,high);   /*  对高子表递归排序 */
 }
}

在主函数QSort中参数传入的参数分别为数组L(我们假设为{50,10,90,30,70,40,80,60,20})和最小下标值low、最大下标值high，Partition函数的操作为选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大。我们将这样的关键字称为枢轴（pivot）。而后面的递归调用则是对枢轴的左边和右边重复调用Partition函数，直到顺序全部正确为止。

下面我们就来看看快速排序最关键的Partition函数实现是怎么样的。

/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
1 int Partition(SqList *L,int low,int high)
2 { 
3  int pivotkey;
4  pivotkey=L->r[low];  /* 用子表的第一个记录作枢轴记录 */
5  while(low<high)      /* 从表的两端交替地向中间扫描 */
6  { 
7    while(low<high&&L->r[high]>=pivotkey)
8    high--;
9    swap(L,low,high); /* 将比枢轴记录小的记录交换到低端 */
10    while(low<high&&L->r[low]<=pivotkey)
11    low++;
12    swap(L,low,high); /* 将比枢轴记录大的记录交换到高端 */
13  }
14  return low;     /* 返回枢轴所在位置 */
15 }

该函数就是将下标为low(最小下标值)的值当作枢轴记录，然后通过判断与下标为high(最大下标值)的值，如果大于了则不会进行调换，如果low<high，并且下标为high的值>枢轴那么high–(即最大下标上一个值继续进行判断)，如果小于则调换位置并将low++(即最小下标下一个值继续进行判断)，以此类推直到顺序正确为止。

快速排序的就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

2.快速排序优化

对于快速排序的枢轴而言，每次选取的对象都是第一个的，在某些最坏情况下去查找，会使得效率大大降低，所以就有了三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。

我们来看看取左端、右端和中间三个数的实现代码，在Partition函数上的第3行下面增加这样一段代码。

int m = low + (high - low) / 2;  /* 计算数组中间的元素的下标 */  
if (L->r[low]>L->r[high])   
 swap(L,low,high);    /* 交换左端与右端数据，保证左端较小 */
if (L->r[m]>L->r[high])
 swap(L,high,m);    /* 交换中间与右端数据，保证中间较小 */
if (L->r[m]>L->r[low])
 swap(L,m,low);    /* 交换中间与左端数据，保证左端较小 */

试想一下，我们对数组{9,1,5,8,3,7,4,6,2}，取左9，中3，右2来比较，使得L.r[low]=3，一定要比9和2要来得更为合理。

三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（median-of-nine），它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的pivotkey是比较接近中间值的关键字。

那么通过上述代码的优化对于Partition函数而言，也可以再进行优化，我们可以将交换改为覆盖替换(因为最后一次的遍历也就是到数组列表中间交换，而我们已经获取到了中间那一个参数，也就是优化后的枢轴pivotkey)，而我们要做的就是通过哨兵(L->r[0])保存枢轴值，那么效率上也会又所提高。

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{ 
 int pivotkey;
 int m = low + (high - low) / 2;  /* 计算数组中间的元素的下标 */  
 
 if (L->r[low]>L->r[high])   
  swap(L,low,high);    /* 交换左端与右端数据，保证左端较小 */
  
 if (L->r[m]>L->r[high])
  swap(L,high,m);    /* 交换中间与右端数据，保证中间较小 */
  
 if (L->r[m]>L->r[low])
  swap(L,m,low);    /* 交换中间与左端数据，保证左端较小 */
  
 pivotkey=L->r[low];  /* 用子表的第一个记录作枢轴记录 */
 L->r[0]=pivotkey;   /* 将枢轴关键字备份到L->r[0] */
 while(low<high)   /* 从表的两端交替地向中间扫描 */
 { 
   while(low<high&&L->r[high]>=pivotkey)
   high--;
   L->r[low]=L->r[high]; /* 采用替换而不是交换的方式进行操作 */
   while(low<high&&L->r[low]<=pivotkey)
   low++;
   L->r[high]=L->r[low]; /* 采用替换而不是交换的方式进行操作 */
 }
 L->r[low]=L->r[0];   /* 将枢轴数值替换回L.r[low] */
 return low; /* 返回枢轴所在位置 */
}

但是对于这些考虑是在数组非常大的情况下才有相对优势，那么在对于数组非常少的时候用这样的方法，那么就像画蛇添足一样了，还不如用之前的方法，所以我们在进行对于这个Qsort函数进行优化。

#define MAX_LENGTH_INSERT_SORT 7  /* 数组长度阀值 */
/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort(SqList &L,int low,int high)
{ 
 int pivot;
 if((high-low)>MAX_LENGTH_INSERT_SORT) /*当high-low大于常数时快速排序*/
 {
  pivot=Partition(L,low,high);  /* 将L.r[low..high]一分为二，算出枢轴值pivot */
  QSort(L,low,pivot-1);   /* 对低子表递归排序 */
  QSort(L,pivot+1,high);   /* 对高子表递归排序 */
 }
 else        /* 当high-low小于等于常数时用直接插入排序 */

  InsertSort(L); 
}

改进了之后，我们发现该函数是一个递归函数，且还有两次递归回溯，每次回溯都会消耗一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。

于是我们对QSort实施尾递归优化。来看代码：

/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort1(SqList *L,int low,int high)
{ 
 int pivot;
 if((high-low)>MAX_LENGTH_INSERT_SORT)
 {
  while(low<high)
  {
   pivot=Partition1(L,low,high); /*  L.r[low..high]一分为二,算出枢轴值pivot */
   QSort1(L,low,pivot-1);   /* 对低子表递归排序 */
   low=pivot+1;     /* 尾递归 */
  }
 }
 else
  InsertSort(L);
}

我们这里通过while(low<high)替换了两次递归的成本。

因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition(L,low,high)，其效果等同于QSort(L,pivot+1,high);。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。

八、各大排序算法评估

从算法的简单性来看，我们将七种算法分为两类

• 简单算法：冒泡、简单选择、直接插入。
• 改进算法：希尔、堆、归并、快速。

从平均情况来看，显然后三种改进算法要胜过希尔排序，并远远胜过前三种简单算法。

从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑四种复杂的改进算法。

从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。

总之，从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对它。