C数据结构：排序

发布于：2025-09-01 ⋅ 阅读:(17) ⋅ 点赞:(0)

C数据结构：排序

1.插入排序
2.希尔排序
3.选择排序
4.快速排序
5.归并排序
6.计数排序
7.排序总结

1.插入排序

数组arr的长度为n，假定下标[0,end]对应的元素有序，把arr[end+1]与下标为[0,end]对应的元素比较，从而找到合适位置插入arr[end+1]，使[0,end+1]有序。

void InsertSort(int* a, int n)//插入排序
{
	for (int i = 0;i < n - 1;i++)
	{
		int end = i;
		int t = a[end + 1];
		while (end >= 0)
		{
			if (t < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
				break;
		}
		a[end + 1] = t;
	}
}

例如数组arr[]={2,1,1,3}。
在这里插入图片描述
进入while循环，比较t与arr[end]的大小，执行if语句，把arr[end]的值覆盖到arr[end+1]，end再自减1。
在这里插入图片描述
由于end<0，跳出while循环，把t赋值给此时的arr[end+1]。
在这里插入图片描述
进入下一次for循环，i变为1。
在这里插入图片描述
此时t又小于arr[end]，再把arr[end]的值覆盖到arr[end]。
在这里插入图片描述
此时，t=arr[end]，执行break，跳出while循环，再把t的值赋给arr[end+1]。
在这里插入图片描述
进入新一轮for循环，i为2，end更新为2，t变为3。
在这里插入图片描述
进入while循环，t>arr[end]，执行break，跳出while循环，再把t赋给arr[end+1]，arr[end+1]仍为3，排序完成。从这里也可看到，for循环的循环条件必须是i<n-1，若i<n，则i=n-1时，end+1就越界了。

插入排序的特性：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定（相同值在数组中相对顺序经排序后仍不变，则为稳定）

2.希尔排序

希尔排序是插入排序的优化，先选定一个整数gap，从首元素开始，每隔gap距离就把元素分为一组，然后控制gap进行循环，当gap>1时为预排序，让数组接近有序，当gap=1时，为插入排序。

void ShellSort(int* a, int n)//希尔排序
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1保证最后一个gap一定是1，gap>1时为预排序，gap=1时为插入排序
		for (int i = 0;i < n - gap;i++)
		{
			int end = i;
			int t = a[end + gap];
			while (end >= 0)
			{
				if (t < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = t;
		}
	}
}

设数组a[10]={9,1,2,5,7,4,8,6,3,5}，数组长度为10，即gap=10。进入while循环，gap变为4，即for循环的循环条件为i<6，进入for循环。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
最终执行完一次for循环，数据变得有序。
在这里插入图片描述
接下来进入新一轮while循环，gap变为2，执行for循环。当再次进入while循环后gap变为1，我们把代码中for循环部分的gap全部换为1，就与插入排序的代码一样了。

希尔排序的特性：

  1. gap越大，大的数越快跳到后面，小的数越快跳到前面，相对越不接近有序
  2. gap越小，跳得越慢，但越接近有序
  3. 时间复杂度：O(N^1.3)
  4. 空间复杂度：O(1)
  5. 稳定性：不稳定

3.选择排序

选择排序遍历一遍数组，找出最小值，然后与首元素交换，除去首元素后再遍历一遍数组，找出最小值，与数组下标为1的元素交换，如此循环往复，直到只剩一个元素。优化后，我们可以一次遍历就取得最小最大值，分别放在数组的首尾，缩小区间，再次遍历。

void Swap(int* p1, int* p2)//交换
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}

void SelectSort(int* a, int n)//选择排序
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin + 1;i <= end;i++)//循环一次，找到最大最小值，放到最左最右边，
		{                                   //缩小区间，再进入新循环。
			if (a[i] > a[maxi])
				maxi = i;
			if (a[i] < a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);
		if (begin == maxi)
			maxi = mini;
		Swap(&a[end], &a[maxi]);
		begin++;//缩小区间
		end--;
	}
	
}

以数组a[8]={9,1,2,5,7,4,6,3}为例。执行完第一次for循环后如图所示：
在这里插入图片描述
把数组中最小元素放到下标为0的位置出，即交换a[begin]和a[mini]。
在这里插入图片描述
此时，数组中最大值被换到了下标为mini的位置，如果直接交换a[maxi]和a[end]，最小值就会被换到数组的最后，排序结果就会出错。所以需要判断当下标begin=maxi时，由于先执行了交换a[begin]和a[mini]，最大值被换到了下标为mini的位置，要把maxi更新为mini，再交换a[maxi]和a[end]。
在这里插入图片描述
在这里插入图片描述
最后缩小区间，进入新一轮的while循环。
在这里插入图片描述
选择排序的特性：

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

4.快速排序

hoare法

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

我们一般把首元素作为基准值。

void QuickSort1(int* a, int left, int right)//快速排序：hoare法
{
	if (left >= right)//不存在的区间
		return;
	int key = left;
	int begin = left, end = right;
	while (begin < end)
	{
		while (begin < end && a[end] >= a[key])//end找比a[key]小的数
			end--;
		while (begin < end && a[begin] <= a[key])//begin找比a[key]大的数
			begin++;
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[key]);
	key = begin;    //[left,key-1] key [key+1,right]
	QuickSort1(a, left, key - 1);
	QuickSort1(a, key + 1, right);
}

以数组a[10]={6,1,2,7,9,3,4,5,10,8}为例，进入循环前如图所示。
在这里插入图片描述
当a[end]<a[key]时，end停下；当a[begin]>a[key]时，begin停下。此时交换a[end]和a[begin]。
在这里插入图片描述
在这里插入图片描述
end走到a[end]=3时，end停下，begin开始走，当begin=end时，不满足begin<end，begin停下，交换a[begin]和a[end]，此时相当于自己和自己交换。
在这里插入图片描述
跳出外层while循环，交换a[key]和a[begin]，让key=begin，分割出左右区间，再分别对两区间排序，即递归。
在这里插入图片描述
在这里插入图片描述
问题： 下标0做key，右边end先走时，为什么begin和end相遇位置一定比a[key]小？

若begin遇到end，因为end停下的位置对应的元素一定比a[key]小，所以相遇位置比a[key]小。若end遇到begin，end未遇到比a[key]小的元素就与begin相遇，由于经过上一轮交换，此时a[begin]<a[key]，所以相遇位置比a[key]小。

相反，让最右边做key，左边begin先走，可保证相遇位置比a[key]大。

hoare法优化

三数取中： 当待排序数组已经是有序时，再使用快排会出现效率退化，end要走到最左边才能开始交换、递归。所以，我们在排序前取最左边元素a[left]、中间元素a[mid]、最右边元素a[right]，比较后得到中间大小的元素，将它与首元素交换后作为a[key]。

int GetMidi(int* a, int left, int right)//三数取中
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else
			return a[left] < a[right] ? right : left;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else
			return a[left] < a[right] ? left : right;
	}
}

小区间优化： 当区间内元素较少时，不必再递归分割排序，改为插入排序，可减少递归次数，防止栈溢出，并提升效率。

优化后的代码如下：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	if ((right - left + 1) < 10)//小区间优化，当区间内元素较少时，不再递归分割排序。减少递归次数。
		InsertSort(a + left, right - left + 1);
	else
	{
		int begin = left, end = right;
		int midi = GetMidi(a, left, right);//三数取中
		Swap(&a[midi], &a[begin]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] >= a[key])
				end--;
			while (begin < end && a[begin] <= a[key])
				begin++;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[key], &a[begin]);
		key = begin;
		QuickSort2(a, left, key - 1);
		QuickSort2(a, key + 1, right);
	}
}
前后指针法

用prev、cur表示数组下标，初始时，prev指向首元素，cur指向prev指向的下一个元素。每次循环cur都要走一步，当a[cur]>=a[key]时，prev也走，当a[cur]<a[key]，且prev走了一步后未与cur相遇时，交换a[prev]和a[cur]。直到cur越界时，停止循环，交换a[prev]和a[key]。

int PartSort(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);//三数取中
	Swap(&a[left], &a[midi]);
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = PartSort(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

仍以a[10]={6,1,2,7,9,3,4,5,10,8}为例。
在这里插入图片描述
在这里插入图片描述
如果a[cur]>a[key]，则不执行交换，prev也不移动，这样的操作使prev和cur之间的元素全是大于a[key]的元素。
在这里插入图片描述
在这里插入图片描述

快排：非递归

我们使用数据结构中的栈，将区间[0,n]存入栈中，再将区间取出作为前后指针法函数的参数进行排序，接下来分出右左区间入栈，进入新循环。

void QuickSortNonR(int* a, int left, int right)//快排：非递归
{
	ST st;//创建栈
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	while (!STEmpty(&st))//一次循环相当于一次递归
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
		int key = PartSort(a, begin, end);//前后指针，单趟排序
		if (key + 1 < end)//右区间入栈
		{
			STPush(&st, end);
			STPush(&st, key + 1);
		}
		if (begin < key - 1)//左区间入栈
		{
			STPush(&st, key - 1);
			STPush(&st, begin);
		}
	}
}

在这里插入图片描述
快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

在这里插入图片描述

5.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
在这里插入图片描述
此算法要借助一个数组中转。

void _MergeSort(int* a, int* t, int begin, int end)//a中数据分解，谁小谁先放入t,最后把t拷贝给a
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;//后序遍历
	_MergeSort(a, t, begin, mid);
	_MergeSort(a, t, mid + 1, end);//[begin,mid]和[mid+1]区间内数据有序就开始归并
	int begin1 = begin, end1 = mid;//归并
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			t[i++] = a[begin1++];
		else
			t[i++] = a[begin2++];
	}  //循环结束后，要么begin1走完，要么begin2走完
	while (begin1 <= end1)//begin2走完，begin1未走完
		t[i++] = a[begin1++];
	while (begin2 <= end2)//begin1走完，begin2未走完
		t[i++] = a[begin2++];
	memcpy(a + begin, t + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)//归并排序
{
	int* t = (int*)malloc(n * sizeof(int));
	if (t == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, t, 0, n - 1);
	free(t);
	t = NULL;
}
归并排序：非递归
void MergeSortNonR(int* a, int n)//归并排序：非递归
{
	int* t = (int*)malloc(n * sizeof(int));
	if (t == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;//一次归并中，参与归并的两组数据中每组有gap个数
	while (gap < n)
	{
		for (int i = 0;i < n;i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;//区间[begin1,end1]
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//区间[begin2,end2]
			if (begin2 >= n)//第二组区间都越界不存在，不用归并这一组
				break;
			if (end2 >= n)//第二组begin2没越界，end2越界，修正后归并
				end2 = n - 1;
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					t[j++] = a[begin1++];
				else
					t[j++] = a[begin2++];
			}  //循环结束后，要么begin1走完，要么begin2走完
			while (begin1 <= end1)//begin2走完，begin1未走完
				t[j++] = a[begin1++];
			while (begin2 <= end2)//begin1走完，begin2未走完
				t[j++] = a[begin2++];
			memcpy(a + i, t + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;
	}
	free(t);
	t = NULL;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

6.计数排序

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

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n)//计数排序
{
	int min = a[0], max = a[0];
	for (int i = 1;i < n;i++)//找出a中最大最小元素
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;//待排序数组在区间[min,max]内有几个元素
	int* count = (int*)calloc(range, sizeof(int));//count储存的是a中某元素在a出现的次数
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	for (int i = 0;i < n;i++)//a[i]-min使a中元素对应数组count的下标
		count[a[i] - min]++; //a中某元素出现一次，count中对应下标的元素加1
	int j = 0;
	for (int i = 0;i < range;i++)
	{
		while (count[i]--)
			a[j++] = i + min;
	}
	free(count);
}

计数排序的特性总结：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,range))
  3. 空间复杂度：O(range)
  4. 稳定性：稳定

7.排序总结

在这里插入图片描述
在这里插入图片描述

拙作一篇，望诸位同道不吝斧正。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布