C语言数据结构之内部排序及其时间复杂度

谁借莪１个温暖的怀抱￠ 2022-12-02 04:10 135阅读 0赞

## C语言数据结构之内部排序及其时间复杂度 ##

tips：前些天学习了查找的方法，今天来总结一下九大内部排序。

--------------------

**先总览一下九大内部排序：**

<table> 
 <tbody> 
 <tr> 
 <th>内部排序</th> 
 <th>插入排序</th> 
 <th>直接插入排序</th> 
 </tr> 
 <tr> 
 <th>折半插入排序</th> 
 </tr> 
 <tr> 
 <th>希尔排序</th> 
 </tr> 
 <tr> 
 <th>交换排序</th> 
 <th>冒泡排序</th> 
 </tr> 
 <tr> 
 <th>快速排序</th> 
 </tr> 
 <tr> 
 <th>选择排序</th> 
 <th>简单选择排序</th> 
 </tr> 
 <tr> 
 <th>堆排序</th> 
 </tr> 
 <tr> 
 <th colspan="2">归并排序</th> 
 </tr> 
 <tr> 
 <th colspan="2">基数排序</th> 
 </tr> 
 </tbody> 
</table>

--------------------

**下面来逐个看看内部排序的过程**

--------------------

**1、直接插入排序**

直接插入排序是在有序序列中插入元素，使其仍然有序。

思路：

*  在原来序列中寻找插入位置k；
 *  将原来序列中从k开始的元素全部后移一位；
 *  在位置k插入新元素；

具体实现：

//直接插入排序（数组0号下标不存放关键字）
 //在有序序列插入值，使其重新有序
 void InsertSort(int arr[], int n)
 {
 
 	int i, j;
 	for (i = 2; i < n; i++)//第一个元素本身有序，所以从编号为2的元素开始插入排序
 	{
 
 		arr[0] = arr[i];//做一个标记,使每次插入有序
 		for (j = i - 1; arr[0] < arr[j]; j--)//寻找合适位置插入
 			arr[j + 1] = arr[j];
 		arr[j + 1] = arr[0];//插入元素(此时arr[0]>=arr[j])
 	}
 }

--------------------

**2、折半插入排序**

折半插入排序是在寻找插入位置时，用折半查找进行定位。

折半插入排序思路与直接插入排序思路相同。

具体实现：

//折半插入排序(用折半查找定位)（数组0号下标不存放关键字）
 void BInsertSort(int arr[], int n)
 {
 
 	int i, j;
 	int low, mid, high;
 	for (i = 2; i < n; i++)//第一个元素自身有序，因此从第二个元素开始插入
 	{
 
 		arr[0] = arr[i];//做一个标记，使每次插入有序
 		low = 1;
 		high = i - 1;
 		while (low <= high)//用折半查找，确定插入位置
 		{
 
 			mid = (low + high) / 2;
 			if (arr[mid] > arr[0])
 				high = mid - 1;//查找前半部分
 			else
 				low = mid + 1;//查找后半部分
 		}//循环结束，插入位置为high+1
 		for (j = i - 1; j >= high + 1; j--)//将high+1以后的元素后移
 			arr[j + 1] = arr[j];
 		arr[high + 1] = arr[0];//插入元素
 
 	}
 
 }

**注意：只有折半查找的循环条件是low<=high，其它不带“=”。**

--------------------

**3、希尔排序**

希尔排序也叫缩小增量排序，希尔排序根据所选步长，将原表分成若干个特殊子表，然后**对子表分别进行直接插入排序**，待整个表元素基本有序时，再对整体进行一次直接插入排序。  
希尔排序步长选取：d1=⌊n/2⌋;d2=⌊d1/2⌋;直到dk=1；

思路：

*  根据所选步长，划分子表；
 *  对子表分别进行直接插入排序；
 *  待整个表元素基本有序时，再对整体进行一次直接插入排序；

具体实现：

//希尔排序（数组0号下标不存放关键字）
 void ShellSort(int arr[], int n)
 {
 
 	for (int dk = n / 2; dk >= 1; dk = dk / 2)//缩小增量，直到增量为1
 	{
 
 		for (int i = dk + 1; i < n; i++)//对每个子表分别进行插入排序
 		{
 
 			if (arr[i] < arr[i - dk])//选取合适位置插入
 			{
 
 				arr[0] = arr[i];//0号元素作为标记
 				int j;
 				for (j = i - dk; j > 0 && arr[0] < arr[j]; j = j - dk)//元素移动
 					arr[j + dk] = arr[j];
 				arr[j + dk] = arr[0];//插入元素
 			}		
 		}
 	}
 }

--------------------

**4、冒泡排序**

思路：

*  从后往前依次两两比较相邻元素的值（冒泡）
 *  符合条件就进行交换；
 *  直到序列比较结束；

具体实现：

//冒泡排序（数组下标从0开始）
 void BubbleSort(int arr[], int n)
 {
 
 	for (int i = 0; i < n - 1; i++)//冒泡执行的次数(最后一个元素就不需要再冒泡了)
 	{
 
 		int flag = 0;
 		for (int j = n - 1; j > i; j--)//一趟冒泡过程
 		{
 
 			if (arr[j - 1] > arr[j])
 			{
 
 				swap(arr[j - 1], arr[j]);
 				flag = 1;
 			}
 		}
 		if (flag == 0)//不发生交换时，证明有序
 			return;
 	}
 }

--------------------

**5、快速排序**

思路：

* 在原表中，任取一个元素作为pivot；
 * 通过pivot，将原表分割(Partition)成两个子表，子表左边全部小于pivot，子表右边全部大于pivot；
 * 直到原表整个有序(low<high)；

Partition分割思路：

*  初始化标记low为划分部分第一个元素位置，high为最后一个元素位置，不断移动并交换元素；
 *  high向前移动找到第一个比pivot小的元素；
 *  low向后移动找到第一个比pivot大的元素；
 *  交换当前两个位置元素；
 *  继续移动标记，直到low>=high位置；

具体实现：

//快速排序
 //快速排序的分割函数
 int Partition(int arr[], int low, int high)
 {
 
 	int pivot = arr[low];//取low下标的元素为关键字
 	while (low < high)
 	{
 
 		while (low < high&&arr[high] >= pivot) 
 			high--;//从后往前找到比关键字小的元素
 		arr[low] = arr[high];//小的，放在左侧部分
 
 		while (low < high&&arr[low] <= pivot)
 			low++;//从前往后找到比关键字大的元素
 		arr[high] = arr[low];//大的，放在右侧部分
 	}
 	arr[low] = pivot;//将关键字放在中间位置(左边全部比关键字小，右边全部比关键字大)
 	return low;//返回中间元素下标
 }
 
 //快速排序主体
 void QuickSort(int arr[], int low, int high)
 {
 
 	if (low < high)
 	{
 
 		int pivot = Partition(arr, low, high);
 		//依次对两个子表进行划分
 		QuickSort(arr, low, pivot - 1);
 		QuickSort(arr, pivot + 1, high);
 	}
 }

--------------------

**6、选择排序**

思路：

*  每趟在待排元素中选择关键字最小的元素放入前面部分；
 *  直到做完n-1趟；

具体实现：

//选择排序
 void SelectSort(int arr[], int n)
 {
 
 	for (int i = 0; i < n - 1; i++)//第一次选择出最小的，第二次选择出次小的...剩下最后一个元素不用选择
 	{
 
 		int min = i;
 		for (int j = i + 1; j < n; j++)
 		{
 
 			if (arr[j] < arr[min])
 				min = j;//选出最小元素下标
 		}
 		if (min != i)
 			swap(arr[i], arr[min]);//交换
 	}
 }

--------------------

**7、堆排序**

思路：

对所有具有双亲结点的编号从大到小依次做如下调整：

*  若孩子结点全部小于双亲结点，则不进行调整；
 *  若存在孩子结点大于双亲结点，则将最大孩子结点与双亲结点交换，并对孩子结点也做相同调整，直到出现双亲结点值最大；

具体实现：

//堆排序
 //建立大根堆（编号从1开始，编号为0的下标不存放关键字）
 void BuildMaxHeap(int arr[], int len)
 {
 
 	for (int i = len / 2; i > 0; i--)//将父结点调整为父结点值均大于孩子结点值
 		AdjustDown(arr, i, len);
 }
 
 //堆排序的调整方法
 void AdjustDown(int arr[], int k, int len)
 {
 
 	arr[0] = arr[k];//用arr[0]存放根结点值
 	
 	for (int i = 2 * k; i <= len; i = i * 2)//(遍历，找所有子树)将以k结点为根结点的子树全部调整为根值最大
 	{
 
 		if (i < len&&arr[i] < arr[i + 1])//比较左右子树的值，选取大的再与根结点比较
 			i++;
 		if (arr[0] >= arr[i])
 			break;//根结点值大于左右子树，不进行调整
 		else
 		{
 
 			//将左右子树最大的值作为根结点的值，再依次向下调整为大根堆
 			arr[k] = arr[i];//大值放到根结点
 			k = i;//修改k的值，向下筛选
 		}
 		arr[k] = arr[0];//将原根结点的值放到arr[i]
 	}
 }
 
 //堆排序主体
 void HeapSort(int arr[], int len)
 {
 
 	BuildMaxHeap(arr, len);//建立大根堆
 	for (int i = len; i > 1; i--)//每次遍历，就将大根堆最大值放入数组最后，再将剩余的元素调整为大根堆
 	{
 
 		swap(arr[i], arr[1]);
 		AdjustDown(arr, 1, i - 1);
 	}
 }

--------------------

**8、归并排序**

(二路归并排序)  
思路：

* 将原表划分成两个一组的子表，并进行排序；
 * 归并两个相邻有序子表，使其成为一个新的有序子表；
 * 直到整个表有序（low<high）；

具体实现：

//归并排序
 //归并排序的合并两个有序线性表方法
 //int brr[11];//头文件中声明
 void Merge(int arr[], int low, int mid, int high)//mid将arr划分成两个子序列
 {
 
 	int i, j, k;
 	for (k = low; k <= high; k++)
 		brr[k] = arr[k];//将arr中的值全部赋予brr
 
 	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
 	{
 
 		if (brr[i] <= brr[j])//比较brr左右两段元素
 			arr[k] = brr[i++];//将较小的放入arr中
 		else
 			arr[k] = brr[j++];
 	}
 	//下面两个while只有一个会执行，用来将剩余的值放回
 	while (i <= mid)
 		arr[k++] = brr[i++];
 	while(j<=high)
 		arr[k++] = brr[j++];
 }
 
 //归并排序主体
 void MergeSort(int arr[], int low, int high)
 {
 
 	if (low < high)
 	{
 
 		int mid = (low + high) / 2;//从中间划分两个子树
 		MergeSort(arr, low, mid);//对左子树排序
 		MergeSort(arr, mid + 1, high);//对右子树排序
 		Merge(arr, low, mid, high);//归并两个有序序列
 	}
 }

--------------------

**9、基数排序**

暂且略-\_-

--------------------

实现完上述排序，接下来我们在main()函数中测试一下;

int main()
 {
 
 	int arr1[10] = {
 10,3,1,5,6,9,8,7,4,2 };//0号下标存放数组长度
 	//直接插入排序
 	InsertSort(arr1, 10);
 	printf("直接插入排序：");
 	for (int i = 1; i < 10; i++)
 	{
 
 		printf("%d ", arr1[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr2[10] = {
 10,3,1,5,6,9,8,7,4,2 };//0号下标存放数组长度
 	//折半插入排序
 	BInsertSort(arr2, 10);
 	printf("折半插入排序：");
 	for (int i = 1; i < 10; i++)
 	{
 
 		printf("%d ", arr2[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr3[10] = {
 10,3,1,5,6,9,8,7,4,2 };//0号下标存放数组长度
 	//希尔排序
 	ShellSort(arr3, 10);
 	printf("希尔排序：");
 	for (int i = 1; i < 10; i++)
 	{
 
 		printf("%d ", arr3[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr4[10] = {
 0,3,1,5,6,9,8,7,4,2 };//值从0号下标开始
 	//冒泡排序
 	BubbleSort(arr4, 10);
 	printf("冒泡排序：");
 	for (int i = 0; i < 10; i++)
 	{
 
 		printf("%d ", arr4[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr5[10] = {
 0,3,1,5,6,9,8,7,4,2 };//值从0号下标开始
 	//快速排序
 	QuickSort(arr5, 0, 9);
 	printf("快速排序：");
 	for (int i = 0; i < 10; i++)
 	{
 
 		printf("%d ", arr5[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr6[10] = {
 0,3,1,5,6,9,8,7,4,2 };//值从0号下标开始
 	//选择排序
 	SelectSort(arr6, 10);
 	printf("选择排序：");
 	for (int i = 0; i < 10; i++)
 	{
 
 		printf("%d ", arr6[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr7[10] = {
 10,3,1,5,6,9,8,7,4,2 };//0号下标存放数组长度
 	//堆排序
 	HeapSort(arr7, 9);
 	printf("堆排序：");
 	for (int i = 1; i < 10; i++)
 	{
 
 		printf("%d ", arr7[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 	int arr8[10] = {
 10,3,1,5,6,9,8,7,4,2 };//0号下标存放数组长度
 	//归并排序
 	MergeSort(arr8, 1, 9);
 	printf("归并排序：");
 	for (int i = 1; i < 10; i++)
 	{
 
 		printf("%d ", arr8[i]);
 	}
 	printf("\n-----------------------------------\n");
 
 
 	return 0;
 	
 }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]

--------------------

**10、内部排序时间复杂度分析**

<table> 
 <thead> 
 <tr> 
 <th>排序算法</th> 
 <th>最好时间复杂度</th> 
 <th>平均时间复杂度</th> 
 <th>最坏时间复杂度</th> 
 <th>空间复杂度</th> 
 <th>稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>直接插入排序</td> 
 <td>O(n)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>冒泡排序</td> 
 <td>O(n)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>简单选择排序</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>希尔排序</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td>O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>快速排序</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( l o g 2 n log_2n log2n)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>堆排序</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>2路归并排序</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n l o g 2 n log_2n log2n)</td> 
 <td>O(n)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>基数排序</td> 
 <td>O(d(n+r))</td> 
 <td>O(d(n+r))</td> 
 <td>O(d(n+r))</td> 
 <td>O( r )</td> 
 <td>稳定</td> 
 </tr> 
 </tbody> 
</table>

--------------------

tips：努力到无能为力，拼搏到感动自己。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/88072f69a2824b7998a4ff84963c201c.png