【数据结构和算法】— 基于c语言排序算法的实现（1）

目录

• 一、排序的概念及其应用
• • 1.1排序的概念
  • 1.2 排序的应用
  • 1.3 常见的排序算法
• 二、插入排序
• • 2.1直接插入排序
  • 2.2 希尔排序
  • • 2.2.1 预排序
    • 2.2.2 缩小gap
    • 2.2.3 小结
• 三、选择排序
• • 3.1 直接选择排序
  • 3.2 堆排序

一、排序的概念及其应用

1.1排序的概念

排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序： 数据元素全部放在内存中的排序。
外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 排序的应用

以下是 “软科中国大学排名” 情况，这便是日常生活中排序的应用，此处排序标准为，以各个大学的总分作为唯一标准，进行降序排序。 此处的排序便是由排序算法实现，下面将对不同的排序算法进行剖析。

1.3 常见的排序算法

下面将基于c语言，对以上七种排序逐一实现。

二、插入排序

2.1直接插入排序

基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
我们可以将直接插入排序想象成玩扑克牌，即每当我们拿到一张牌，然后插入到我们手上已排好序的牌中，从小到大直到找到合适的位置然后插入，以此循环直到排完序为止。
依据上述方法，我们可以先排数组的前两个数。第一个数作为已排好序的数组，第二个数作为要插入数组的数，插入完成后，将上述所有已插入的数作为已排好序的数组，然后再向后取一个数执行上述逻辑。 以此作为循环的主体，直到取完数组中所有的数，即当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

代码实现：

//直接插入排序
void InsertSort(int* a, int n)
{
	for(int i = 0; i < n - 1; i++)
	{
		//[0, end] 已排好序的数组
		int end = i;
		int tmp = a[end + 1];//要插入的数
		//tmp 向前比较 -- 小于前一个数，则 a[end] 向后拷贝，end--，继续比较前一个数
		//大于则说明 tmp 到了合适的位置
		while(end >= 0)
		{
			if(tmp <= a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//比较完成，插入！
		a[end + 1] = tmp;
	}
}

代码实现时几点注意：

• 确定好要以排好序的数组范围(下标为0 ~ n - 2)，n -1位置是最后一个要插入的数；
• 要插入的数为已排好序的数组最后一个元素(end = i)的下一个(tmp = a[end + 1)，使用tmp记录；
• tmp向前比较，小于a[end]则继续比较前一个，当前a[end]向后拷贝，并使end--；直到tmp大于a[end]，或end < 0，则结束，并使a[end] = tmp。

直接插入排序动态演示：

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高；
2. 时间复杂度： O(N^2)；
3. 空间复杂度： O(1)，它是一种稳定的排序算法；
4. 稳定性： 稳定

2.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

根据元素集合越接近有序，直接插入排序算法的时间效率越高的规律，那么我们可以想方法先把一堆数据排的接近有序（预排序），然后再进行直接插入排序。

2.2.1 预排序

可以定义gap来表示每次预排序的元素的跨度（即每次趟排序的数组下标相隔的值），这时gap也表示整个数组要排序的趟数。大致如下图所示：

gap趟中的每一趟，又是直接插入排序。那么在直接插入排序的基础上，我们只需要控制一下初始值，下标增值和结束条件即可，如：for(int j = i; j < n - gap; j += gap)，其中n - gap是因为，每趟排序的最后一个元素都在整个数组的后gap个，又因为直接插入排序最后一个位置不取，所以要< n - gap。代码如下：

//预排序（以 gap = 3 为例）
int gap = 3;
//gap 趟
for(int i = 0; i < gap; i++)
{
	//直接插入排序
	for(int j = i; j < n - gap; j += gap)
	{
		int end = j;
		int tmp = a[end + gap];
		while(end >= 0)
		{
			if(tmp <= a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp; 
	}
}

当然还可以对上面代码进行一点小优化，可以将外层两个for循环改成一个：for(int j = 0; j < n - gap; j++)。 事实上循环总次数是不变的，我们只是将原来先排好第一组再排后面组的思路，改成了混在一起排，效果还是一样的。由一组一组排变为了多组并排。

2.2.2 缩小gap

有了预排序，那么我们只要合理的控制gap的大小，便完成了希尔排序。如：gap = gap / x + 1，其中的x可以根据具体的待排序的数组的长度来决定。 待排序数组长，则x设置较大一些；待排序数组短，则x设置较小一些。gap / x后还要加一，是为了让排序的最后一趟gap = 1，即直接插入排序。

//希尔排序（缩小增量排序）
void ShellSort(int* a, int n)
{
	int gap = n;
	//gap > 1 时是预排序，目的是让他接近有序
	//ga[ = 1 时是直接插入排序，目的是让他有序
	while(gap > 1)
	{
		gap = gap / 3 + 1;  //加1是为了让他最后一次 gap = 1
		//预排序
		// ....
	}
}

排序整体逻辑基本如下：

2.2.3 小结

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。如此一来，当gap == 1时，数组已经接近有序的了，这样效率也会很高。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：
   《数据结构(C语言版)》— 严蔚敏
   
   《数据结构-用面相对象方法与C++描述》— 殷人昆
   
   因为咋们的gap是按照 Knuth 提出的方式取值的，而且 Knuth 进行了大量的试验统计，我们暂时就按照：O(N^1.25)到 O(1.6 * N^1.25)来算。
4. gap越大，大的值越快跳到后面，小的值越快跳到前面，越不接近有序；gap越小，大的之越慢跳到后面，小的值越慢跳到前面，越接近有序；
5. 稳定性： 不稳定

三、选择排序

3.1 直接选择排序

基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接插入排序动态演示：

上述的方法是从头遍历到尾，找最小值，然后插入到目标位置，事实上效率并不是很高，于是我们可以这样进行点小优化：定义一个变量int begin = 0，从下标为begin的位置向后找小，再定义一个变量int end = n - 1，从下标为begin的位置向后找大，待循环结束大值和下标为end的值交换，小值和下标为begin的值交换，然后begin++; end--;，直到begin == end排序结束。这样每次循环都会找到两个目标值，且缩小了下一次搜索的范围，达到了优化的效果。
代码实现：

//直接插入选择（优化）
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	//记录 较大值 和 较小值 的下标
	int mini = begin, maxi = degin;
	while(begin < end)
	{
	    //找大值和小值
		for(int i = begin + 1; i < end + 1; i++)
		{
			if(a[i] < a[mini])
				mini = i;
			if(a[i] > a[maxi])
				maxi = i;
		}
		//交换
		Swap(&a[begin], &a[mini]);
		//判断防止最大值丢失
		if(maxi == begin)
			maxi = mini;
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

还有一点需要注意的是，交换完一个值我们要先判断，看最大值是否在begin位置，if(maxi == begin)，若在，则将maxi换到mini位置。逻辑大致如下：

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1)
4. 稳定性： 不稳定

3.2 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
因为之前已经介绍过了，所以这里就不多讲了，详细请参考：【数据结构和算法】—二叉树（2）–堆的实现和应用

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(1)
4. 稳定性： 不稳定