C语言实现：希尔排序、插入排序、归并排序、堆排序详解

分手后的思念是犯贱 2022-03-17 05:53 225阅读 0赞

*由于算法的设计，导致自定义排序函数没有问题，但是在输出的时候，对于下标的选择要仔细，否则结果会发生错误。*  
（四）插入排序第一类：直接插入排序算法：讲一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。它的原理类似于我们的扑克牌摸牌再将牌插入到一个合适的位置的操作类似，如果我们整理手中扑克牌的顺序是从小到大整理，现在我们开始摸牌，第一张是5，在摸一张牌我们发现是8，那按照我们的整理顺序，我们直接将8放在5的右侧完成插入，在摸一张我们发现是6，通过与8的比较，我们会将8向右移动一位然后与5进行比较发现比5大，那么我们就将6放在8移走了之后空出来的那个位置上…以此类推。

void sort(int *a, int length)		//直接插入排序 
    {
    	int i, j;
    	for(i = 2;i <= length;i++)
    	{
    		if(a[i] < a[i - 1])
    		{
    			a[0] = a[i];		//设置哨兵
    			for(j = i - 1;a[j] > a[0];j--)
    				a[j + 1] = a[j];	//元素后移 
    			a[j + 1] = a[0];	//插入到正确位置  
    		}
    	}
    }

插入排序第二类：折半插入排序，这有些类似于数组的二分查找，我们将对数组中元素的查找方法改成了折半查找，由于折半查找比顺序查找快，因此折半插入排序的平均性能就比直接插入排序要快。算法如下：

void sort(int *a, int length)		//折半插入 
    {
    	int tem, i ,j ,low, high, mid;
    	for(i = 1;i < length;i++)			//扩大有序表 
    	{
    		tem = a[i];
    		low = 0;
    		high = i - 1;
    		while(low <= high)			//类似于二分查找算法
    		{
    			mid = (low + high) / 2;
    			if(tem < a[mid])		//第一次可以比较a[0]和a[1]的大小 
    				high = mid - 1;
    			else
    				low = mid + 1;
    		}
    		for(j = i - 1;j >= low;j--)
    		{
    			a[j + 1] = a[j];		//其后的元素一起后移 
    		}
    		a[low] = tem;			//插入待排元素 
    	}
     }

（五）希尔排序：又称缩小增量排序 ，设计思路是：假设待排序列有n个元素，首先选取一个整数i（i < n）作为间隔,将全部元素分成i个子序列，将所有距离为i的元素放在同一个子序列中，对每一个子序列进行插入排序，这个时候，我们的序列就变得**基本有序**。注意，基本有序的意思是整个数组元素大致满足正确的排序序列，然后（例如）我们令i = i / 2（当然也可以是i / 3等等），重复上述的子序列划分和排序工作，直到最后i取值为1，将所有的元素放在同一个序列中排序为止。例程如下：

void shellsort(int *a, int length)		//希尔排序 
    {
    	int i, j;
    	int increment = length;
    	do
    	{
    		increment = increment / 3;		//增量序列的选择
    		for(i = increment + 1;i <= length;i++)
    		{
    			if(a[i] < a[i - increment])
    			{
    				a[0] = a[i];		//将此值暂存在a[0]中
    				for(j = i - increment;j > 0 && a[0] < a[j];j -= increment)
    					a[j + increment] = a[j]; 	//数据后移，寻找要插入的位置 
    				a[j + increment] = a[0];	//插入到头 
    			}
    		}
    	}while(increment > 1);
    }

通过上面的代码，我们可以看出希尔排序的关键在于他不是随便分组后各自排序，而是经过了一定的“距离”实现了跳跃式的移动，是的排序效率提高。  
那么这里的“距离”的选取就变的非常关键了，我们的代码中选用了length / 3的方法来选取，那到底采用哪一种方法选取“距离”最好呢？很遗憾，目  
前这仍然是一个数学难题，但时仍然有学者给出了下图中的两种增量序列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
由于记录的移动式跳跃式的，因此希尔排序是一种不稳定的算法。  
（六）堆排序：我们假设利用大顶堆进行排序的方法。基本思想为：首先将一个待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，将他移走（就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩下的n - 1个序列重新构造成一个堆，这样就会得到n个元素中得到次大值。如此反复执行，就会得到一个有序序列了。如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
堆排序的大致算法如下：

void heap_sort(int *a, int length)		//堆排序 
    {
    		int i;
    		for(i = length / 2;i > 0;i--)
    			build_heap(a, i, length);	//建一个大顶堆
    		for(i = length;i > 1;i--)
    		{
    			swap(a, 1, i);		//将堆顶记录与当前未排序的子序列的最后一个记录交换 
    			build_heap(a, 1, i - 1);	//将剩下的元素重新调成大顶堆 
    		}
    }

从代码中我们可以看出整个排序过程分为两个for循环，第一个循环要完成的就是将待排序列构建成一个大顶堆，第二个循环是要将每个最大的值的根节点与末尾元素交换，并再次将其调整为大顶堆。

那么我们接下来应该解决两个问题：  
1.如何由无序序列建立一个堆？  
2.如果在输出堆顶元素后，调整剩下的元素成为一个新的堆？  
我们先给出建堆的算法：

void build_heap(int *a, int s, int m)
    {
    	int tem, j;
    	tem = a[s];
    	for(j = 2 * s;j <= m;j *= 2)		//沿关键字较大的节点向下筛选 
    	{
    		if(j < m && a[j] < a[j + 1])
    			++j;					//j为关键字中较大的下标 
    		if(tem >= a[j])
    			break;
    		a[s] = a[j];
    		s = j; 
    	}
    	a[s] = tem;		//插入 
    }

第一个for循环为什么要2 \* s呢？因为我们的树是完全二叉树，那么加入当前节点的序号是s他的左孩子序号一定是2s，右孩子节点序号一定是2s + 1，他们的孩子当然也是以2的位数序号增加，因此j是这样的循环。  
**注意：在用大顶堆进行排序的时候，我们的第一个元素通常作为预备元素，也就是说，数组中下标为0的位置不放置数据或者放置不在待排序列中的数据**。否则输出数组元素的时候会出现错误。  
（七）归并排序：就是利用归并的思想实现排序的方法，它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n / 2个长度为2或1的有序子序列，在两两归并，重复上述操作，直到得到一个长度为n的有序序列为止，这种方法称为2路归并排序。

void merge(int *a, int *b, int i, int m, int n)
    {
    	int j, k, e;
    	for(j = m + 1, k = i;i <= m && j <= n;k++)
    	{
    		if(a[i] < a[j])
    			b[k] = a[i++];
    		else
    			b[k] = a[j++];
    	}
    	if(i <= m)
    	{
    		for(e = 0;e <= m - i;e++)
    			b[k + e] = a[i + e];		//将a数组剩余的前半部分复制到b中 
    	}
    	if(j <= n)
    	{
    		for(e = 0;e <= n - j;e++)
    			b[k + e] = a[j + e];		//将a数组后半部分剩余的复制到b中 
    	 } 
    }
    
    void msort(int *a, int *b, int s, int t)
    {
    	int m;
    	int TR2[t + 1];
    	if(s == t)
    		b[s] = a[s];
    	else
    	{
    		m = (s + t) / 2;		//将原数组一分为二
    		msort(a, TR2, s, m);	//递归的归并前半部分为有序的TR2
    		msort(a, TR2, m + 1, t);	//递归的归后半部分为有序的TR2
    		merge(TR2, b, s, m, t);	//将两个TR2归并到TR1 
    	}
    }

该算法我们采用了递归的方式来进行，因此在空间复杂度上我们需要额外的深度为log2n的栈空间，因此空间复杂度为O（n + logn），我们在merge函数中有if的判断语句，这就是说他需要两两进行比较，不存在跳跃，所以归并排序是一种较稳定的排序算法。在时间复杂度上面，一趟归并需要将数组a的相邻长度为h的有序序列进行两两归并，并将结果放到数组b中，这需要将数组全部扫描一遍，需要耗费O（n）的时间， 而由完全二叉树的深度可知，整个归并排序需要进行log2n次，因此，总的时间复杂度为O（nlogn），而且这是归并排序算法中最好、最坏、平均时间性能。综上所述，归并排序是一种比较占内存，但效率却高且稳定的算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220317/f1d8c2d1755743f4848bae412d243c3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220317/389c88d8e56048ba80d3b5d47c53b7f8.png