首页 > 资讯 > 后端开发 > 其他教程 >C语言八大排序算法的过程图解及实现代码

595

分享到

C语言八大排序算法的过程图解及实现代码

2024-04-02 19:04:59 595人浏览独家记忆

摘要

目录前言一、插入排序时间复杂度空间复杂度代码实现（升序）二、希尔排序时间复杂度空间复杂度代码实现三、选择排序时间复杂度空间复杂度代码实现四、堆排序时间复杂度空间复杂度代码实现五、冒泡

前言

排序是数据结构中很重要的一章，先介绍几个基本概念。

排序稳定性：多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

一、插入排序

时间复杂度

最坏：-----------O(N^2)

最好：-----------O(N)

平均：-----------O(N^2)

空间复杂度

O(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++)
	{
		int x = a[end+1];//x为待排序的值
		int end = i;//从end开始往前和x依次比较

		while (end >= 0)
		{
			if (a[end] > x)//只要当前的值大于x继续往前找
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;//跳出循环说明a[end] <= x
			}
		}
		a[end + 1] = x;//跳出循环说明a[end] <= x，需要把x插入到end前边
	}
}

那么我们可以看到，越是接近有序的数组，插入排序的效率越高（有序时对于任何一个数只需要和前边的数比较一次）。

二、希尔排序

时间复杂度

O(n^（1.3—2）)

空间复杂度

O(1)

稳定性：稳定

『希尔排序』(shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

该方法实质上是一种『分组插入』方法,因为插入排序对于接近有序的数组排序效率非常高，那么希尔提出：

算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

并且插入排序可以看成分组是1的希尔排序。动图如下：

因为插入排序可以看做gap==1的希尔排序，因此只需要改变插入排序中for循环的增量控制排序即可。

代码实现


void ShellSort(int* a, int n)
{
	//按gap分组进行预排序
	int gap = n;
	while (gap>1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;//这里分组选每次折半或者/3都可以

		for (int j = 0; j < gap; j++)//gap个组
			for (int i = j; i < n - gap; i+=gap)//每个组从j开始每个增量gap	
			{
				int end = i;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > x)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = x;
			}
	}
}

关于希尔排序时间复杂度证明比较复杂，取决于gap怎么取，如果按照Knuth提出的/3，来取是O(n^（1.25）- 1.6*O(n^1.25).

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

三、选择排序

时间复杂度

最坏：-----------O(N^2)

最好：-----------O(N^2)

平均：-----------O(N^2)

空间复杂度

O(1)

稳定性：不稳定

『基本思想』：

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

代码实现


void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	int mini = begin;//记录最小值下标
	while (begin<end)
	{
		for (int i = begin; i < end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//更新最小值下标
			}
		}
		Swap(&a[mini],&a[begin]);//把最小值放到左边
		++begin;//左边对应起始位置++
	}
}

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。

四、堆排序

时间复杂度

最坏：-----------O(N * logN)

平均：-----------O(N*logN)

空间复杂度

O(1)

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

具体可见另一篇文章堆排序和TopK问题

动图：

代码实现


void Swap(int* px,int* py)
{
	int t = (*px);
	(*px) = (*py);
	 (*py)= t ;
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

五、冒泡排序

时间复杂度

最坏：-----------O(N^2)

最好：-----------O(N)

平均：-----------O(N^2)

空间复杂度

O(1)

『冒泡排序』是大家最熟悉的也是最容易理解的排序,如下图：

『冒泡排序基本思想』就是每一次将相邻的数据进行『两两比较』，选出最大的依次比较送到右边，那么最右边就是最大值，而左边留下的自然就是小的（排升序）

-『冒泡排序』需要两层循环

『内层循环』表示一次冒泡，也就是两两比较先选出最大的放到最右边，同时注意每一次冒泡选出最大元素，那么两两比较次数-1（下一次不用比较选好的最右边）

『外层循环』控制的是冒泡的次数（假设数组N 个元素）也就是N-1次冒泡选出N-1个最大的元素

代码实现

初版代码如下：


//初版：
void Swap(int* px, int* py)
{
	int t = (*px);
	*px = (*py);
	(*py) = t;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)//外层循环
	{
		for (int j = 0; j < n-1-i; j++)
		{
			if(a[j]>a[j+1])
				Swap(&a[j],& a[j + 1]);//交换
			flag = 1;
		}	
	}
}

时间复杂度分析：每一次比较次数是N-1,N-2,N-3***1.因此是N(N-1)/2

但是这种写法还是有缺陷，时间复杂度永远是O(N^2），对于一个已经排好序的数组来说，还是需要N^2的复杂度，但对于有序的数组，每一次冒泡都不会进行交换因为有序，因此如果只要任何一次冒泡中没有数据交换就证明数组有序了。时间复杂度最好也可以达到0(N)。

代码优化如下：


//优化：
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n-1-i; j++)
		{
			if(a[j]>a[j+1])
			Swap(&a[j],& a[j + 1]);
			flag = 1;
		}
		if (flag == 0)
			break;

	}
}

六、快排排序

时间复杂度

最坏：-----------O(N^2)

最好：-----------O(logN)

平均：-----------O(logN)

空间复杂度

O(logN)

『快速排序』是Hoare于1962年提出的一种二叉树结构的交换排序方法，其『基本思想』为：任取待排序元素序列中的某元素作为『基准值』，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。如图：

代码实现

递归写法：


// 假设按照升序对a数组中[left, right)区间中的元素进行排序
void QuickSort(int* a, int left, int right) {
	 if(right >= left )
	 	return;//递归截止条件
	 
	 // 按照基准值对a数组的 [left, right]区间中的元素进行划分
	 int keyi= partion(a, left, right);
	 
	 // 划分成功后以keyi为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right]
	 // 递归排[left, keyi-1]
	 QuickSort(a, left, keyi-1);
	 
	 // 递归排[keyi+1, right]
	 QuickSort(a, keyi+1, right);
}

递归框架写完了接下来就差partion函数的实现也就是快排的灵魂，去每一次找基准值。那么一共有三种写法如下：

hoare版本

1.首先就是要找基准值，这里你可以选最左边或最右边的值（图中是6）

2.两个指针指向头（这里选左为基准值，头指针指向第二个）和尾，基准值选左，则右指针先走，反之左指针先走。

3.左指针找到比基准值大的停下，右指针找比基准值小的停下，交换左右指针指向值

4.重复2.3动作，直到左右指针相遇，交换左指针值和基准值

左值为基准，右指针先走找比6小的：

交换：

最终效果：相遇交换左指针和基准值，保证了6的左边都比6小，右边比6大。

并且除此之外，由于我们看到这种算法类似于二叉树的思想排好中间再排左右子树，因此我要保证选取的随机值尽量位与中位数。所以我们采取三数取中的方法。（选取最左值最右最中间的数的中位数）效率是可以提升5%到10%的。


//三数取中
int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	//int mid = left + (right - left) / 2;
	int mid = left + ((right - left)>>1);
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;

		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else 
		{
			return right;
		}
	}
	else//a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;

		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}

}
int Partion(int* a, int left,int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);
	
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}Swap(&a[left], &a[keyi]);
	return left;
}

挖坑法

挖坑法就是对hoare版本的一种变形，过程如下：

初始如下：先保存基准值，基准值形成一个坑位！

左为基准，右指针先走，找到小的送到坑位，那么此刻右指针形成了新的坑位

左指针出动，找到大的继续送到坑位，左指针形成了新的坑位

指针相遇，把6写入。也保证左边比6小，右边比6大。代码如下：


//挖坑法
int Partion2(int* a, int left, int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);

	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		//右边先找小
		while (left< right && a[right] >= key)
		{
			--right;
		}
		a[pivot] = a[right];
		pivot = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}

前后指针版本

顾名思义，使用两个指针，这里选取左为基准值为例，两个指针从左开始出发一个cur,一个prev。

要求：

cur指针先走，一旦找到比基准值小的就停下，++prev,并交换。

cur指针一直到头为止，最后交换prev指向值和基准值

1和2都比6小cur走一步停一步，prev++并交换，指向相等。

cur越过7和9去找小的3，此时停下，prev++指向7交换。（我们注意到prev和cur不等时prev永远是去找大的，cur是找小的，因此交换就做到把cur指向的小的往前扔，大的往后仍，）

整个过程如上，代码：


//前后指针法
int Partion3(int* a, int left, int right)
{
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);
	int prev = left, cur = left+1;
	int keyi = left;
	while (cur<=right)
	{
		if (a[cur] < a[keyi] && ++prev !=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

小结

递归版本三种方法如上，但是递归毕竟有缺陷，就是需要不断开辟栈帧，当数据量超过10W以上时就会有栈溢出的风险。

并且递归类似二叉树的结构越往下递归调用越多，栈帧翻倍开辟，因此我们还可以去优化一下，就是当递归到左右区间比较小时，我们去控制剩下的排序用别的排序来代替它。


//优化：
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	if (right - left + 1 < 10)
	{
		//小区间优化
		InsertSort(a + left , right - left + 1);
	}
	else
	{
		int keyi = Partion3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	
}

非递归：

非递归版本就是改变了快排的框架，用一个栈和循环来代替递归实现。依次将左右下标入栈出栈（出栈之前排序）来模拟递归。


void QuickSortNonR(int* a, int left, int right)
{
	Stack st;//定义一个栈
	StackInit(&st);//初始化
	StackPush(&st, left);//左下标入栈
	StackPush(&st, right);//右下标入栈
	while (StackEmpty(&st)!=0)
	{
		int end = StackTop(&st);//获取栈顶元素即后入栈的右下标
		StackPop(&st);//出栈

		int begin = StackTop(&st);//获取栈顶元素即先入栈的左下标
		StackPop(&st);//出栈

		int keyi = Partion3(a, begin, end);
		if (keyi + 1 < end)//相当于递归左半部分
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
		if (keyi - 1 > begin)//相当于递归右半部分
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}

	}
}

七、归并排序

时间复杂度

最坏：-----------O(NlogN)

最好：-----------O(NlogN)

平均：-----------O(NlogN)

空间复杂度

O(N)

稳定性：稳定

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。动图演示：

归并的思想就是把先假设数组分成两个有序，对其进行筛选排序，如上图：

但是问题来了我们怎么保证数组是有序的？因此就要求我们从小区间开始对数组归并排序，对于上图中的数据，先对开始3和3归并，小的先进入到tmp数组，因此前两个就是有序，再对，5和6归并，5,6有序后，在归并3，3，5，6……以此类推

代码实现

递归写法

框架：


void MergeSort(int* a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//开辟N个大小数组
	if (tmp == NULL)
	{
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//进行归并操作
	free(tmp);
	tmp = NULL;
}

归并排序：

运用递归先不断缩小偏序区间，在递归层层退出时一遍退出，一边对不断回大的区间归并排序：


void _MergeSort(int* a, int left, int right,int* tmp)
{
	if (left >= right)
	{
		return;//递归截止条件left >= right区间中数的个数<=0个
	}
	int mid = left + (right - left) / 2;//取中

	_MergeSort(a, left, mid, tmp);//对左区间递归
	_MergeSort(a, mid+1, right, tmp);//对右区间递归

	int begin1 = left, end1 = mid;//左区间
	int begin2 = mid+1, end2 = right;//右区间
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1 )
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	for (size_t i = left; i <= right; i++)
	{
		a[i] = tmp[i];//把排好序[left,right]的tmp赋值给原数组
	}
}

非递归

非递归的不同就是需要手动控制区间大小，也就是不断2倍扩大区间归并。

但是还需要注意就是当下标是奇数，无法分成整数个组的时候，需要考虑剩余的数，以及是否越界的问题


void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i][i+gap-1] [i+gap][i+2*gap-1]
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = i;


			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}



			while (begin1<=end1 && begin2<=end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//控制越界问题三种情况
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (end1 >= n)
			{
				end1 = n - 1;
			}

			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}

		
		gap *= 2;
	}
	
	free(tmp);
	tmp = NULL;

}

八、计数排序

时间复杂度

最坏：-----------O(MAX(N,范围))

最好：-----------O(MAX(N,范围))

平均：-----------O(MAX(N,范围))

空间复杂度

O(范围)

稳定性：不稳定

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

动图如下：

类似桶排序的思想，如上图，先开辟数组统计数组中某一个数出现的次数，比如2出现1次，3出现两次，那么我们直接按顺序读入开辟的数组，在原数组写1一个2，两个3以此类推……

代码实现


void CountSort(int* a, int n)
{
	int max=a[0], min= a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int)*range);
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

计数排序的特性总结：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

九、各种排序总结比较

1. 复杂度总结

2. 性质分类

以上就是C语言 八大排序算法的过程图解及实现代码的详细内容，更多关于C语言八大排序算法的资料请关注编程网其它相关文章！

--结束END--

本文标题: C语言八大排序算法的过程图解及实现代码

本文链接: https://lsjlt.com/news/159047.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

C语言 八大排序算法的过程图解及实现代码

目录

前言

一、插入排序

时间复杂度

空间复杂度

代码实现（升序）

二、希尔排序

时间复杂度

空间复杂度

代码实现

三、选择排序

时间复杂度

空间复杂度

代码实现

四、堆排序

时间复杂度

空间复杂度

代码实现

五、冒泡排序

时间复杂度

空间复杂度

代码实现

六、快排排序

时间复杂度

空间复杂度

代码实现

七、归并排序

时间复杂度

空间复杂度

代码实现

八、计数排序

时间复杂度

空间复杂度

代码实现

九、各种排序总结比较

C语言八大排序算法的过程图解及实现代码