C语言各种排序算法的总结（一）

相信很多同学对排序算法都有了不同程度的理解，这篇文章仅仅是为了总结一些常用的排序算法的原理，追求更加深入的理解这些排序算法的实现原理，更加细致地去理解代码为什么要这么个写法。虽然真正需要对数据排序的时候没有必要自己再写一个排序算法，直接调用内置函数即可，但是深入地去理解这些算法的实现方式，其实会发现这其中有许多的乐趣，哎！就是玩儿~。
第一次写，欢迎指正~~

一.常用排序算法的种类及其时间复杂度和稳定性

种类	时间复杂度
选择排序法	O(n^2)
冒泡排序法	O(n^2)
插入排序法	O(n^2)
希尔排序法	O(nlog2n)
归并排序法	O(nlog2n)
快速排序法	O(nlog2n)
堆排序法	O(nlog2n)
计数排序	O(n+k)
桶排序	O(n+k)
基数排序	O(n*k)

二.对部分排序算法的解析以及代码实现

1.选择排序法

1.1 工作原理：
对未排序的序列进行遍历，找到最大（小）的元素，将其放在该序列的起始位置。然后再从对未进行排序的序列进行遍历，继续寻找最大（小）的元素，放到该未排序序列的起始位置，以此类推，直到所有元素都排序完毕。

1.2 具体代码实现：

int Selection_Sort(int array[],int size)
{
	int temp;
	for (int i=0; i < size-1; i++)	//外层循环
	{
		for (int j = i + 1; j < n; j++)	//内层循环
		{
			if (array[j] < array[i])	//这个if就是实现比对的过程
			{
				temp = array[j];		//交换元素的过程
				array[j] = array[i];
				array[i] = temp;
			}
		}
	}
	return 0;
}

当然此处函数的传入参数也可以不是数组名而是一个指向数组的指针变量，如*array也是可行的。

1.3 过程分析：
利用两层循环，外层循环遍历序列中的前n-1个元素，因此外层循环的次数应为n-1。内层循环则从当前外层循环遍历到的数的后一个元素开始遍历，直到序列的最后一个元素。这样做的目的是：每次首先假设未排序序列的首元素为最大（小）的元素，通过与后面元素的比对，在一次外层循环结束后得到该未排序序列中的最大（小）值。

实际例子示例：
待排序列：11 37 20 18 8
第一次：8 37 20 18 11
第二次：8 11 20 18 37
第三次：8 11 18 20 37 排序结束

1.4 时间复杂度分析：
首先外层循环要遍历整个序列的n-1个元素，一次外层循环分别对应了n-1,n-2,…,1次的内层循环，因此，总共循环的次数就是(n-1)+(n-2)+…+1=n*(n-1)/2次，n的次数为2，所以时间复杂度为O(n^2)。

2.冒泡排序法

冒泡排序算法跟选择排序算法的不同之处在于选择排序算法是在整个序列中找出最大（小）的元素，而冒泡排序算法是比较相邻的元素，把较大（小）的元素放在前面，该过程就好像气泡冒出水面一样，因此称之为冒泡排序算法。

2.1 工作原理：
对一个序列重复遍历，每次比较两个元素，如果他们的顺序错误，则将他们的顺序进行调换，那么在这样的一次遍历交换的过程之后，这个序列的最后一个元素就是该序列中最大的元素了（看不懂没关系，后面会有实数栗子）。当整个序列的元素没有必要再进行顺序调换时，则遍历结束。

2.2 具体代码实现：

int Bubble_Sort(int array[], int size)
{
	int temp;
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = 0; j < size - 1; j++)
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	return 0;
}

2.3 过程分析：
对于一个包含n个元素的序列，假设要实现从小到大的排序，外层循环的循环次数是考虑该序列排序的最坏情况，也就是该序列从大到小的情况，那么序列起始位置的元素到达末尾需要经历n-1次的交换，因此为了满足该情况，外层循环的次数应该达到n-1次。那么内层循环又在搞什么名堂呢？内层循环其实是在进行比对与交换的工作，那在一次外层循环中到底要进行多少次的内层循环呢？因为前面已经提到了，在一次外层循环结束后，序列的最后一个元素就已经是最大的了，因此倒数第二位的元素没有必要再和最后一位元素进行比对，这就是限制内层循环次数的一个重要条件。

实际例子示例：
待排序列：11 37 20 8 18
i=0：
11 20 8 18 37
i=1:
11 8 18 20 37
i =2:
8 11 18 20 37
再来看一个最坏的情况：
待排序列：5 4 3 2 1
i=0:
4 3 2 1 5
i=1:
3 2 1 4 5
i=2:
2 1 3 4 5
i=3:
1 2 3 4 5

2.4时间复杂度分析：
对于包含n个元素的序列，外层循环执行n-1次，每次外层循环对应的内层循环次数分别为：n-1,n-2,n-3…1次，因此一共需要循环的次数为：(n-1)+(n-2)+…+1=n(n-1)/2,因此时间复杂度为O(n^2)。

3.插入排序法

3.1工作原理：
构建了一个有序的序列，从未排序的序列中抽取元素向有序序列中插入。

3.2具体代码实现：

int Insertion_Sort(int array[], int size)
{
	int i, j, temp;
	for (i = 1; i < size; i++)
	{
			for (j = i; j > 0; j--)
			{
				if (array[j] < array[j - 1])
				{
					temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
			}
	}
	return 0;
}

3.3过程分析：
对于一个包含n个元素的序列，可以看作将这n个元素依次插入到一个已经排好序的序列中，每次插入元素时，对已经排好序的序列从后向前进行扫描，扫描到的每一个数都与要插入的数进行比对，最终将这个数插入到已经排序好的序列中，并不会影响该序列的有序性。其实这种排序方法和冒泡排序如出一辙，都是分别对比两个相邻数的大小，这个插入的过程，其实就是这个数在已经排序好的数列中向自己应该所处的位置“冒”。
这里再细致地分析一下内层循环的执行机制，令j=i,让a[j]与a[j-1]进行比对，如果没有满足后一个数大于前一个数的条件，那么内层循环将不会执行if的语句，也就是说后续j会自减至j=0从而结束外层循环。

实际例子演示：

待排序列：11 37 20 8 18
【11】37 20 8 18
【11 37】20 8 18
【11 20 37】8 18
【8 11 20 37】18
【8 11 18 20 37】

对于我们人类而言，我们在运用这个插入排序的时候，就是一个简简单单的插入的动作，因为我们可以直接 判断出这个待插入的数应该处于哪个位置，但是机器他笨呐（小丑是我自己）~，他就需要一个一个数去比对，这个插入的过程对于机器来说其实还是一个数值位置转换的过程，只不过最后呈现出来的效果是这个数插进去了。

3.4 时间复杂度分析：
外层循环循环了n-1次，内层循环分别执行1，2，3…n-1次，所以一共执行了1+2+3+…+(n-1)=n*(n-1)/2次的循环，因此时间复杂度为O(n^2)。

可以发现选择排序法，冒泡排序法以及插入排序法，虽然实现算法的方式和原理不一样，但是他们的时间复杂度是相同的。

4.希尔排序法

这个算法他🐂🍺啊(虽然不是最🐂的一个)！但是他首次突破了O(n^2)的时间复杂度，让排序变得更快咯。就像那句话说的“向前一小步…”，啊~ 不是，应该是“我的一小步，人类的一大步”，就是内味。其实了解了希尔排序算法后，就相当于了解了冒泡和插入排序法了，因为插入排序包含了冒泡排序，而希尔排序又是插入排序的改进版，他们就是一环套一环的关系~

4.1 工作原理：
将整个待排序列进行分组，分组的方式是设置一个间隔，每经过一个间隔就取出对应的数放入组中。然后再对不同组的元素进行插入排序。在经过一次分组插入排序后，将间隔减半，再次分组，再次进行分组插入排序。以此类推，一直到最终分组时只分得一个组也就是间隔为1的情况，最后进行一次插入排序，最终排序结束。

4.2具体代码实现：

int Shell_Sort(int array[], int size)
{
	int i, j, gap, temp;
	for (gap = size / 2; gap > 0; gap /= 2)	//第一层循环：确定分组间隔，并且缩减间隔
	{
		for (i = gap; i < size; i++)	//第二层循环
		{
			for (j = i - gap; j -gap>=0 && array[j-gap]>array[j]; j -= gap)
			{
				temp = array[j];
				array[j] = array[j-gap];
				array[j - gap] = temp;
			}
		}
	}
	return 0;
}

4.3 过程分析：
首先来看一下第一层循环在搞什么东东，可以看到定义了gap（分组间隔）为待排序列长度的1/2，并且当gap>0时，每次第一层循环都会让gap变为原本的1/2，从而达到缩减间隔的目的，可以得知最终gap将会变为1，也就是把整个序列作为了一组。

再来看看第二层循环：他的语法到底在表达什么意思呢？对于这段语句，个人认为应当结合上第三层循环共同理解。实际上第二与第三层循环进行的工作是，对分隔后的小组进行直接插入排序（第三种介绍的排序算法）。那么如何在一个整体序列中对分组序列进行插入排序呢？如果我用python的话，我一定会把这些分好组的元素抽出来放进不同的数组里面，这样整个过程中运用的逻辑思维难度就降低了不少。然而…但是…可是，现在我们在利用C语言来解决这个问题，所以就需要一定的思维逻辑来进行实现，逻辑如下（可能是我比较愚笨所以觉得很巧妙）：
利用实例进行讲解：

待排序列：
55 2 6 4 32 12 9 73 （共8个元素）
gap=8/2=4
第一次分组情况为：
一. 55 9 >>>> 9 55
二. 2 73 >>>> 2 73
三. 6 26 >>>> 6 26
四. 4 37 >>>> 4 37
排序后： 9 2 6 4 55 73 26 37
gap=4/2=2
第二次分组情况为：
一. 9 6 55 26 >>>> 6 9 26 55
二. 2 4 73 37 >>>> 2 4 37 73
排序后：6 2 9 4 32 12 55 73
gap=2/2=1
第三次分组情况为：
一.6 2 9 4 32 12 55 73 >>>> 2 4 6 9 12 32 55 73

那么以上分组插入排序的过程是如何通过代码实现的呢？
我们再次回到第二与第三次循环中来，并通过第二次分组来演示代码执行过程。第二次排序前的序列为: 6 2 9 4 32 12 55 73,令i=gap=2，就是让i指向第三个数9，此后第二次循环将遍历9（包括9）以后的所有元素。而第三层循环做的工作就是让i指向的数插入到前面的已经排序好的序列中去,j = i-gap;j-gap>=0;j-=gap表达的意思就是让j去扫描排好序的序列中的各个元素，以确定i指向的元素应当插入到哪个位置（其实就是插入排序的过程）。
实际上，这个分组插入的过程是交替性进行的，也就是说不是第一组排序完毕后，再进行第二，三…n组的排序，而是第一组排序>第二组排序>…>第n组排序，然后再重复进行第一组排序>第二组排序>…>第n组排序。这个逻辑就是理解第二三层循环的关键。

4.4 时间复杂度分析：
实际上希尔排序算法的时间复杂度与增量序列的定义有关系，当增量序列为{1,2,4,8…}（也是该程序的增量序列）时，最坏情况的时间复杂度可以达到O(n^ 2), Hibbard提出的增量序列{1,3,7…,2^ k-1}（质数增量），最坏情况下的时间复杂度为O(n^ 2/3)，Sedge提出的几种增量序列最好的一个{1,5,19,41,109…}在最坏情况下的时间复杂度为O(n^1.3)。

好了，这篇先写这么多，下一篇再介绍快速排序，归并排序，堆排序等等的排序算法，然后再补充一下时间复杂度的数学分析。