改进排序算法（C语言实现）

港控/mmm° 2023-01-07 15:26 110阅读 0赞

继续开始对排序算法进行整理。

### 文章目录 ###

*  一、希尔排序
 *  二、堆排序
 *  三、归并排序
 *  四、快速排序
 *  五、小结

# 一、希尔排序 #

> 希尔排序是D.L.Shell于1959年所提出的一种改进插入排序算法，在这之前排序算法的时间复杂度基本都是 O ( n 2 ) O(n^2) O(n2),希尔排序是突破这个时间复杂度的第一批算法之一。  
> 该算法的核心工作就是要保证数据“基本有序而且记录少”，这是由于插入排序算法对记录较少的数据具有更好的处理效果，其实现过程是采用了“跳跃分割”的策略，这其实有点类似于一些图像的滤波处理方法，先使用较大的步长对数据进行“粗排序”，之后再减少步长对数据进行“精排序”，最终实现将数据按顺序排列。更为详细的步骤可以参考小甲鱼老师的视频[【C语言描述】《数据结构和算法》（小甲鱼）][C]，讲的非常好。代码实现如下：

> main.c

#include<stdio.h>
    #include<stdlib.h>
    #include"Practice.h"
    
    int main()
    { 
    	int arr[]={ 9,2,8,3,4,5,1,0,6,7},
    		length=sizeof arr/sizeof arr[0],i;
    		
    		ShellSort(arr,length);
    		for(i=0;i<length;i++)
    		{ 
    			printf("%d ",arr[i]);
    		}
    	printf("\n");
    
    	return 0;
    }

> Practice.h

//****************************************
    //声明部分
    //****************************************
    
    void ShellSort(int arr[],int length);				//希尔排序（应用到插入排序之中）
    
    //****************************************
    //定义部分
    //****************************************
    //希尔排序
    void ShellSort(int arr[],int length)
    { 
    	int i,j,temp;
    	int stride=length;
    	do
    	{ 
    		stride=stride/3+1;		//步长
    
    		for(i=stride;i<length;i++)
    		{ 
    			if(arr[i] < arr[i-stride])
    			{ 
    				temp=arr[i];
    
    				for(j=i-stride; arr[j]>temp && j>-1;j-=stride)
    				{ 
    					arr[j+stride]=arr[j];
    				}
    
    				arr[j+stride]=temp;
    			}
    		}
    
    	}while(stride>1);
    }

运行结果：  
![在这里插入图片描述][20210118145110494.png]

> 这里的步长选取是非常关键的，怎样选取合适的步长直至现在依旧是一个数学难题，不过倒是有研究得出了一些结论，具体使用效果仍要视情况而定。特别要注意的是，步长的最小值必须等于1才行。由于记录是跳跃式移动的，所以该算法并不是一个稳定的排序算法。

# 二、堆排序 #

> 我们都见过叠罗汉，一群人最终把一个人给顶到一个很高的位置，而“堆”就是类似于叠罗汉的一种数据结构（也就是完全二叉树）。堆排序算法是Floyd和Williams在1964年共同发明的，这是一种改进的选择排序算法，所以该算法的核心工作就是“更快的找到数据中的最大值或最小值”。

> 按照数据的分布情况，堆可以分为大顶堆与小顶堆两类，从名字就可以看出是大顶堆是指每个结点的值都大于或等于其左右孩子结点值的堆结构（如下图所示），反之，若是每个结点的值都小于或等于其左右孩子结点值，则称为小顶堆。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]

> 假设按照层序遍历的方式给结点从1开始编号，用数学语言描述则结点之间满足如下关系：

\{ k i ≥ k 2 i k i ≥ k 2 i + 1 或 \{ k i ≤ k 2 i k i ≤ k 2 i + 1 1 ≤ i ≤ ⌊ n / 2 ⌋ \\begin\{cases\} k\_i \\geq k\_\{2i\} \\\\ k\_i \\geq k\_\{2i+1\}\\\\ \\end\{cases\} 或 \\begin\{cases\} k\_i \\leq k\_\{2i\} \\\\ k\_i \\leq k\_\{2i+1\}\\\\ \\end\{cases\} 1 \\leq i\\leq \\lfloor\{n/2\}\\rfloor \{ ki≥k2iki≥k2i\+1或\{ ki≤k2iki≤k2i\+11≤i≤⌊n/2⌋

不过要使用数据来构建上述的堆结构，除了上述的关系式之外，还要利用一些完全二叉树的性质。：

> 假设数据的个数为 n n n，如果 i > 1 i>1 i>1，  
> 1、 则其双亲是结点 ⌊ n / 2 ⌋ \\lfloor\{n/2\}\\rfloor ⌊n/2⌋。  
> 2、如果 2 i > n 2i>n 2i>n,则结点 i i i没有左孩子。  
> 3、如果 2 i < n 2i<n 2i<n，则结点 i i i没有右孩子。

利用这些关系与性质，即可通过代码实现对排序，如下所示：

> main.c

#include<stdio.h>
    #include<stdlib.h>
    #include"Practice.h"
    
    int main()
    { 
    	int arr[]={ -1,9,2,8,3,4,5,1,0,6,7},		//为了方便编号第一个数弃用
    		length=sizeof arr/sizeof arr[0],i;
    	HeapSort(arr,length-1);
    	
    	for(i=1;i<length;i++)
    	{ 
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

> Practice.h

//堆排序（改进的选择排序）
    
    //将第一个元素与最后一个元素进行互换
    void swap(int arr[],int start,int end)
    { 
    	int temp=arr[start];
    	arr[start]=arr[end];
    	arr[end]=temp;
    }
    
    //调整堆上节点的数值
    HeapAdjust(int arr[],int s,int length)			
    { 
    	int i,temp;
    	temp=arr[s];
    
    	for(i=2*s;i<=length;i*=2)
    	{ 
    		if(i<length && arr[i]<arr[i+1])		//判断左孩子是否小于右孩子
    		{ 
    			i++;		//指向大孩子
    		}
    
    		if(temp >= arr[i])		//判断父节点是否大于等于两个子节点
    			break;
    
    		arr[s] = arr[i];
    
    		s = i;
    	}
    
    	arr[s] = temp;		//最后更改的节点，将初始的值赋给该节点
    }
    
    //堆排序
    void HeapSort(int arr[],int length)		//仍然是每次选择出一个最大或最小值（只不过是通过构建大顶堆和小顶堆）
    { 
    	int i;
    
    	for(i=length/2;i>0;i--)				//这里的length/2是为了求出父节点的个数
    	{ 
    		HeapAdjust(arr,i,length);			//调整堆上第 i 个节点的数值，从上到下，从右至左
    	}
    
    	for(i=length;i>0;i--)
    	{ 
    		swap(arr,1,i);		//将第一个元素与最后一个元素进行互换
    		HeapAdjust(arr,1,i-1);			//重新调整堆上的元素,因为修改了第一个元素
    	}
    
    }

> 堆排序算法的运行时间主要都是消耗在了构建堆和在重建堆上。特别要注意的是，在构建堆的过程中需要从小往上来构建，这有点类似于许多赛事的季后赛，队伍之间进行PK，胜者进入下一轮，败者止步本轮。  
> 而且由于对排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为 O ( n l o g n ) O(nlogn) O(nlogn)，不过该算法中所涉及到的比较与交换是跳跃式进行的，所以其也是一种不稳定的算法，而且另一方面，其由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

# 三、归并排序 #

> 归并有合并之意，因此归并排序就是利用合并的思想来实现的排序方法。不过欲要合并必先分割，分割的方法主要有两种方式，一种是递归进行分割（递归），而另一种则是与希尔排序有些相似的跳跃分割（迭代）。

> 递归方式实现归并排序，其基本过程就是先分割到底（将数据分割至最小颗粒）再进行合并，代码实现如下所示：

#define MAXSIZE 20
    //归并排序（递归实现,先分再合，也就是先分到最小颗粒再进行合并）
    
    void Merge(int *left,int left_size,int *right,int right_size)
    { 
    	int temp[MAXSIZE];			//临时存放排序结果的地方
    	int i,j,k,m;
    	i=j=k=0;
    
    	while(i<left_size && j<right_size)
    	{ 
    		if(left[i]<right[j])		//判断左右两边数值大小
    		{ 
    			temp[k++]=left[i++];
    		}
    		else
    		{ 
    			temp[k++]=right[j++];
    		}
    	}
    
    	while(i<left_size)			//处理剩下的数据
    	{ 
    		temp[k++]=left[i++];
    	}
    
    	while(j<right_size)
    	{ 
    		temp[k++]=right[j++];
    	}
    
    	for(m=0;m<(left_size+right_size);m++)			//将排序好的数据重新写入到相应位置中，从左往右
    	{ 
    		left[m]=temp[m];
    	}
    }
    
    //归并排序
    void MergeSort(int arr[],int length)	
    { 
    	if(length>1)
    	{ 
    		int *left=arr;		//左边部分
    		int left_size = length/2;
    		int *right=arr+length/2;		//右边部分
    		int right_size = length -left_size;
    
    		MergeSort(left,left_size);		//递归过程，左边与右边
    		MergeSort(right,right_size);
    		
    		Merge(left,left_size,right,right_size);		//将左边与右边进行合并
    	}
    }

> 而迭代方式（跳跃分割）实现归并排序，其过程则是边分割边合并，实现代码如下：

//归并排序（迭代实现,边分割边合并）
    void MergeSortIteration(int arr[],int length)
    { 
    	int i,left_min,left_max,right_min,right_max,next;
    	int *temp=(int *)malloc(length*sizeof(int));		//用于记录排序结果的临时数组
    
    	for(i=1;i<length;i*=2)		//步长,从1开始
    	{ 
    		for(left_min=0;left_min<length-i;left_min=right_max)
    		{ 
    			left_max=left_min+i;
    			right_min=left_max;
    			right_max=right_min+i;
    
    			if(right_max>length)
    			{ 
    				right_max=length;
    			}
    
    			next = 0;		//记录指向下一个索引
    
    			while(left_min<left_max && right_min<right_max)
    			{ 
    				if(arr[left_min]<arr[right_min])
    				{ 
    					temp[next++]=arr[left_min++];
    				}
    				else
    				{ 
    					temp[next++]=arr[right_min++];
    				}
    				
    			}
    
    			while(left_min<left_max)
    			{ 
    				arr[--right_min]=arr[--left_max];			//将左边剩余部分移动到最右边
    			}
    
    			while(next>0)
    			{ 
    				arr[--right_min]=temp[--next];
    			}
    		}
    	}
    
    	free(temp);
    }

> 该算法的总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，而且迭代实现的归并排序，又避免了递归时深度为 l o g 2 n log\_2n log2n的栈空间，这更是进一步使得该算法得到提升。除此之外，该算法在诸多改进算法中是一种相对稳定的算法。

# 四、快速排序 #

> 快速排序最早是由图灵奖获得者Tony Hoare所提出的一种改进的冒泡算法，被誉为20世界十大算法之一。与普通的冒泡排序相比其虽然也是通过不断的比较和移动交换来实现排序的，但是它增大了记录比较与移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比价次数和移动交换次数。其基本的思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

其实现过程如下所示：

//快速排序
    
    int Partition(int arr[],int low,int high)	//设置基准点
    { 
    	int point=arr[low];		//初始化基准点
    
    	while(low<high)
    	{ 
    		while(low<high && arr[high]>=point)		//判断索引的大小，并将比基准点大的数值放在基准点右边
    		{ 
    			high--;
    		}
    
    		swap(arr,low,high);	
    
    		while(low<high && arr[low]<=point)		//判断索引的大小，并将比基准点小的数值放在基准点左边边
    		{ 
    			low++;
    		}
    
    		swap(arr,low,high);	
    	}
    
    	return low;		//返回基准点的位置
    
    }
    
    void QSort(int arr[],int low,int high)
    { 
    	int point_index;
    
    	if(low<high)
    	{ 
    		point_index = Partition(arr,low,high);		//获取基准点索引
    
    		QSort(arr,low,point_index-1);		//分成两个部分进行处理，数值小的一部分
    
    		QSort(arr,point_index+1,high);		//数值大的一部分
    	}
    	
    }
    
    void QuickSort(int arr[],int length)
    { 
    	QSort(arr,0,length-1);
    }

在上述代码之中，就最坏情况而言，其最终的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，但是就平均情况而言，其数量级又为 O ( n l o g n ) O(nlogn) O(nlogn)。而且同上面算法一样的理由，该方法仍然是一个不稳定的排序方法。

> 为了避免发生最坏的排序情况，在原始的快速排序的基础上，我们还可以做一些基础优化。

> 1、优化选取枢轴（基准点）

//改进快速排序（优化基准点）
    
    int ImprovedPartition(int arr[],int low,int high)	//获取基准点索引
    { 
    	int point;		//初始化基准点
    	int mid=(low+high)/2;	//改进选择的基准点
    	
    	if(arr[low]>arr[high])
    	{ 
    		swap(arr,low,high);
    	}
    
    	if(arr[mid]>arr[high])
    	{ 
    		swap(arr,mid,high);
    	}
    
    	if(arr[mid]>arr[low])
    	{ 
    		swap(arr,mid,low);
    	}
    
    	point=arr[low];		//使的arr[low]的值为三者中间的那个值
    
    	while(low<high)
    	{ 
    		while(low<high && arr[high]>=point)		//判断索引的大小，并将比基准点大的数值放在基准点右边
    		{ 
    			high--;
    		}
    
    		swap(arr,low,high);	
    
    		while(low<high && arr[low]<=point)		//判断索引的大小，并将比基准点小的数值放在基准点左边边
    		{ 
    			low++;
    		}
    
    		swap(arr,low,high);	
    	}
    
    	return low;		//返回基准点的位置
    
    }
    
    void ImprovedQSort(int arr[],int low,int high)
    { 
    	int point_index;
    
    	if(low<high)
    	{ 
    		point_index = ImprovedPartition(arr,low,high);		//获取基准点索引
    
    		ImprovedQSort(arr,low,point_index-1);		//分成两个部分进行处理，数值小的一部分
    
    		ImprovedQSort(arr,point_index+1,high);		//数值大的一部分
    	}
    	
    }
    
    void ImprovedQuickSort(int arr[],int length)
    { 
    	ImprovedQSort(arr,0,length-1);
    }

> 2、优化交换过程

//改进快速排序（优化交换过程）
    
    int ImprovedPartition2(int arr[],int low,int high)	//获取基准点索引
    { 
    	int point;		//初始化基准点
    	int mid=(low+high)/2;	//改进选择的基准点
    	
    	if(arr[low]>arr[high])
    	{ 
    		swap(arr,low,high);
    	}
    
    	if(arr[mid]>arr[high])
    	{ 
    		swap(arr,mid,high);
    	}
    
    	if(arr[mid]>arr[low])
    	{ 
    		swap(arr,mid,low);
    	}
    	
    	point=arr[low];		//使的arr[low]的值为三者中间的那个值
    
    	while(low<high)
    	{ 
    		while(low<high && arr[high]>=point)		//判断索引的大小，并将比基准点大的数值放在基准点右边
    		{ 
    			high--;
    		}
    
    		arr[low]=arr[high];
    
    		while(low<high && arr[low]<=point)		//判断索引的大小，并将比基准点小的数值放在基准点左边边
    		{ 
    			low++;
    		}
    
    		arr[high]=arr[low];
    	}
    
    	arr[low] = point;
    
    	return low;		//返回基准点的位置
    
    }
    
    void ImprovedQSort2(int arr[],int low,int high)
    { 
    	int point_index;
    
    	if(low<high)
    	{ 
    		point_index = ImprovedPartition2(arr,low,high);		//获取基准点索引
    
    		ImprovedQSort2(arr,low,point_index-1);		//分成两个部分进行处理，数值小的一部分
    
    		ImprovedQSort2(arr,point_index+1,high);		//数值大的一部分
    	}
    	
    }
    
    void ImprovedQuickSort2(int arr[],int length)
    { 
    	ImprovedQSort2(arr,0,length-1);
    }

> 3、优化小数组时的排序方案。这个过程相对简单一些，就是当分割的数组数字个数小于等于7个时（书中说这是经验之谈），使用插入排序算法，否则则使用快速排序算法。

//改进快速排序（优化小数组时的排序策略）
    
    void InsertSort2(int arr[],int low,int high)	//插入排序
    { 
    	/*int i,j,temp; for(i=low+1;i<high+1;i++) { if(arr[i] < arr[i-1]) { temp=arr[i]; for(j=i-1; arr[j]>temp && j>-1;j--) { arr[j+1]=arr[j]; } arr[j+1]=temp; } }*/
    
    	InsertSort(arr+low,high-low+1);		//左闭右开
    }
    
    int ImprovedPartition3(int arr[],int low,int high)	//获取基准点索引
    { 
    	int point;		//初始化基准点
    	int mid=(low+high)/2;	//改进选择的基准点
    	
    	if(arr[low]>arr[high])
    	{ 
    		swap(arr,low,high);
    	}
    
    	if(arr[mid]>arr[high])
    	{ 
    		swap(arr,mid,high);
    	}
    
    	if(arr[mid]>arr[low])
    	{ 
    		swap(arr,mid,low);
    	}
    	
    	point=arr[low];		//使的arr[low]的值为三者中间的那个值
    
    	while(low<high)
    	{ 
    		while(low<high && arr[high]>=point)		//判断索引的大小，并将比基准点大的数值放在基准点右边
    		{ 
    			high--;
    		}
    
    		arr[low]=arr[high];
    
    		while(low<high && arr[low]<=point)		//判断索引的大小，并将比基准点小的数值放在基准点左边边
    		{ 
    			low++;
    		}
    
    		arr[high]=arr[low];
    	}
    
    	arr[low] = point;
    
    	return low;		//返回基准点的位置
    
    }
    
    void ImprovedQSort3(int arr[],int low,int high)
    { 
    	int point_index;
    
    	if(high-low>MAX_LENGTH_INSERT_SORT)
    	{ 
    		point_index = ImprovedPartition3(arr,low,high);		//获取基准点索引
    
    		ImprovedQSort3(arr,low,point_index-1);		//分成两个部分进行处理，数值小的一部分
    
    		ImprovedQSort3(arr,point_index+1,high);		//数值大的一部分
    	}
    	else
    		InsertSort2(arr,low,high);
    	
    }
    
    void ImprovedQuickSort3(int arr[],int length)
    { 
    	ImprovedQSort3(arr,0,length-1);
    }

> 4、优化递归操作

//改进快速排序（使用尾递归）
    
    int ImprovedPartition4(int arr[],int low,int high)	//获取基准点索引
    { 
    	int point;		//初始化基准点
    	int mid=(low+high)/2;	//改进选择的基准点
    	
    	if(arr[low]>arr[high])
    	{ 
    		swap(arr,low,high);
    	}
    
    	if(arr[mid]>arr[high])
    	{ 
    		swap(arr,mid,high);
    	}
    
    	if(arr[mid]>arr[low])
    	{ 
    		swap(arr,mid,low);
    	}
    	
    	point=arr[low];		//使的arr[low]的值为三者中间的那个值
    
    	while(low<high)
    	{ 
    		while(low<high && arr[high]>=point)		//判断索引的大小，并将比基准点大的数值放在基准点右边
    		{ 
    			high--;
    		}
    
    		arr[low]=arr[high];
    
    		while(low<high && arr[low]<=point)		//判断索引的大小，并将比基准点小的数值放在基准点左边边
    		{ 
    			low++;
    		}
    
    		arr[high]=arr[low];
    	}
    
    	arr[low] = point;
    
    	return low;		//返回基准点的位置
    
    }
    
    void ImprovedQSort4(int arr[],int low,int high)
    { 
    	int point_index;
    
    	if(high-low>MAX_LENGTH_INSERT_SORT)
    	{ 
    		while(low < high)
    		{ 
    			point_index = ImprovedPartition4(arr,low,high);		//获取基准点索引
    
    			if(point_index-low < high-point_index)
    			{ 
    				ImprovedQSort4(arr,low,point_index-1);		//减少一个递归调用
    				low = point_index+1;
    			}
    			else
    			{ 
    				ImprovedQSort4(arr,point_index+1,high);
    				high = point_index-1;
    			}
    		}
    		
    	}
    	else
    		InsertSort2(arr,low,high);
    	
    }
    
    void ImprovedQuickSort4(int arr[],int length)
    { 
    	ImprovedQSort4(arr,0,length-1);
    }

# 五、小结 #

这些排序算法之中包含着许多前人天马行空的想法，虽然现在使用代码实现了他们，但是仍有诸多之处心中存有疑虑未能深入了解，他们之中的思想更是知之皮毛，所以后续对它们的运用和理解仍任重道远啊\*~\*。

> 参考资料：《大话数据结构》、[【C语言描述】《数据结构和算法》（小甲鱼）][C]

[C]: https://www.bilibili.com/video/BV1jW411K7yg
[20210118145110494.png]: /images/20221119/df6d22320e5746958fa9216741a8108c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210118171309113.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RheXVoYWl0YW5nMQ==,size_16,color_FFFFFF,t_70