Chapter 6: 排序

标签：Chapter right end int gap 排序 left

在计算机科学中，排序算法是基础且核心的部分，它们被广泛应用于各种领域，如数据处理、信息检索等。C语言作为一种通用的、过程式的计算机程序设计语言，它的运行效率和灵活性使得它成为学习和实现这些排序算法的理想选择。本篇博客将深入探讨一些常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，以及如何使用C语言来实现这些算法。我们将看到如何通过C语言的指针和数组操作，来对一组数据进行有效的排序。希望通过本篇博客，读者能够更好地理解和掌握这些排序算法，以及如何在C语言中实现这些算法。

文章目录

排序的概念及其运用
常见排序算法的实现
排序算法复杂度及稳定性分析
总结

一、排序的概念及其运用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则是不稳定的

内部排序：数据元素全部放在内存中的排序

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

1.2排序运用

1.3 常见的排序算法

// 排序实现的接口
 
// 插入排序
void InsertSort(int* a, int n);
 
// 希尔排序
void ShellSort(int* a, int n);
 
// 选择排序
void SelectSort(int* a, int n);
 
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
 
// 冒泡排序
void BubbleSort(int* a, int n)
 
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
 
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
 
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
 
// 计数排序
void CountSort(int* a, int n)
 
// 测试排序的性能对比
void TestOP()
{
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int)*N);
    int* a2 = (int*)malloc(sizeof(int)*N);
    int* a3 = (int*)malloc(sizeof(int)*N);
    int* a4 = (int*)malloc(sizeof(int)*N);
    int* a5 = (int*)malloc(sizeof(int)*N);
    int* a6 = (int*)malloc(sizeof(int)*N);
 
 for (int i = 0; i < N; ++i)
 {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
 } 
 int begin1 = clock(); 
 InsertSort(a1, N); 
 int end1 = clock();

 int begin2 = clock(); 
 ShellSort(a2, N); 
 int end2 = clock(); 

 int begin3 = clock(); 
 SelectSort(a3, N); 
 int end3 = clock(); 

 int begin4 = clock(); 
 HeapSort(a4, N); 
 int end4 = clock(); 

 int begin5 = clock(); 
 QuickSort(a5, 0, N-1); 
 int end5 = clock(); 

 int begin6 = clock(); 
 MergeSort(a6, N); 
 int end6 = clock();
 printf("InsertSort:%d\n", end1 - begin1);
 printf("ShellSort:%d\n",end2-begin2);
 printf("SelectSort:%d\n",end3-begin3);
 printf("HeapSort:%d\n", end4 - begin4);
 printf("QuickSort:%d\n",end5-begin5);
 printf("MergeSort:%d\n",end6-begin6); 

 free(a1);
 free(a2);
 free(a3);
 free(a4);
 free(a5);
 free(a6);
}

排序OJ (可使用各种排序跑这个OJ ). - 力扣（LeetCode）

冒泡和插入的差异：冒泡几乎每次都情况最坏，插入几乎每次都不是最坏

二、常见排序算法的实现

2.1 插入排序

2.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

实际中玩扑克牌时，就用了插入排序的思想

2.1.2 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

先写单趟，再扩展

单趟：

注意结束时的下标位置，是n-2

时间复杂度考虑最坏情况，逆序的时候最坏，等差数列

参考代码：

//插入排序
//时间复杂度 O(N^2)
//最好情况：逆序
//最好情况：顺序或者接近有序 O(N),遍历了一遍
//
void InsertSort(int* a, int n)
{
	//套一层循环，控制end的起始位置即可
	for (int i = 0; i < n-1; i++)
	{
		//[0,end]end+1
		//第0个数当作是有序的，后一个数往前一个插入
		int end=i;
		int tmp=a[end+1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;//含两种情况
	}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

2.1.3 希尔排序(缩小增量排序)

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

一组内的两个数交换：

代码优化之前是一组一组排，优化后是gap组数据，交替完成分组插入，end一步一步走

参考代码：

//希尔排序
//预排序--目标：接近有序  gap>1
//插入排序--目标：有序    gap == 1
//把1换成gap
void ShellSort(int* a, int n)
{
	  int gap = 3;

	//for (int j = 0; j < gap; j++) //一共有gap组
	//{
	//	for (int i = j; i < n - gap; i += gap)
	//	{
	//		int end=i;
	//		int tmp = a[end + gap];
	//		while (end >= 0)
	//		{
	//			if (tmp < a[end])
	//			{
	//				a[end + gap] = a[end];
	//				end -= gap;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//		a[end + gap] = tmp;
	//	}
	//}

	for (int i = 0; i < n - gap; i++)//代码优化
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)//代码优化
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序了，这样就会很快。这样整体而言，可以达到优化的效果。实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在很多树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

比O(N*logN)更大

因为gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，暂时就按照：

4. 稳定性：不稳定

2.2 选择排序

2.2.1基本思想

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

2.2.2 直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

一个错误示例：

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		//选出最小值和最大值的位置
		int mini = begin, maxi = begin;
		for (size_t i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;

	}
}

maxi和begin重叠了导致的问题，maxi和mini交换了

解决办法：加一个条件判断

//直接选择排序
//优化版本：遍历一遍，选出最小的和最大的数的下标
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		//选出最小值和最大值的位置
		int mini = begin, maxi = begin;
		for (size_t i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;

	}
}

直接选择排序的特性总结：

1. 直接选择排序思考好理解，但效率不是很好，实际中很少使用（暴力选择）

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.2.3 堆排序

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

//堆排序
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;
		}
	}
}

// 升序，建大堆还是小堆呢？大堆
// O(N*logN)
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率高了很多

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

直接选择排序和堆排序大概比较一下：

但是通过测试发现，数据量小的时候和数据量大的时候，二者大小不一，这是因为堆排序数据量大的时候建堆会有不少消耗

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

单趟：

参考代码：

//冒泡排序
//时间复杂度：O(N^2)
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int exchange = 0;
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

2.3.2 快速排序

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

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

上述为快速排序递归实现的主框架，与二叉树前序遍历规则非常像，在写递归框架时可联系二叉树前序遍历规则快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本

不是把左右区间拷贝到子数组处理，向下传下标，递归，是针对原数组处理的

单趟排序：

void PartSort(int* a, int left, int right)
{
	int keyi = a[left];
	while (left < right)
	{
		//right先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
}

右边做key,要让左边先走

参考代码：

void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;

	int begin = left, end = right;
	int keyi = left;
	while (left < right)
	{
		//right先走，找小
		//降序则右边找大<=
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		//降序，左边找小>=
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin,keyi-1]keyi[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

递归展开图：

2. 挖坑法

3. 前后指针版本

参考代码：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = left;
	int prev = left;
	int cur = left+1;

	while (cur <= right)
	{
		//if (a[cur]<a[keyi])
		//{
		//	++prev;
		//	Swap(&a[prev], &a[cur]);
		//	++cur;
		//}

		//简化代码
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

	Swap(&a[keyi], &a[prev]);
	keyi = prev;

	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort2(a, left, keyi - 1);
	QuickSort2(a, keyi + 1, right);
}

2.3.2 快速排序优化

1.随机数选key

//快速排序
//时间复杂度：O(N*logN)
//最坏情况：有序/接近有序->O(N^2)
//但是如果加上随机选key或者三数取中选key,最坏情况不会出现，所以这里不看最坏情况
void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;

	int begin = left, end = right;

	//left不一定是0
	//选[left,right]区间中的随机数做key,最坏情况可能性降低
	int randi = rand()%(right-left+1);//随机值需要在区间内
	randi += left;
	Swap(&a[left], &a[randi]);

	int keyi = left;
	while (left < right)
	{
		//right先走，找小
		//降序则右边找大<=
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		//降序，左边找小>=
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin,keyi-1]keyi[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2.三数取中法选key

//快速排序
//时间复杂度：O(N*logN)
//最坏情况：有序/接近有序->O(N^2)
//但是如果加上随机选key或者三数取中选key,最坏情况不会出现，所以这里不看最坏情况
void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;

	//小区间优化,选择走插入，可以减少90%左右的递归
	if (right - left + 1 < 10)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int begin = left, end = right;

		//left不一定是0
		//选[left,right]区间中的随机数做key,最坏情况可能性降低
		//int randi = rand()%(right-left+1);//随机值需要在区间内
		//randi += left;
		//Swap(&a[left], &a[randi]);

		int midi = GetMidi(a, left, right);
		Swap(&a[left], &a[midi]);

		int keyi = left;
		while (left < right)
		{
			//right先走，找小
			//降序则右边找大<=
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			//left再走，找大
			//降序，左边找小>=
			while (left < right && a[left] <= a[keyi])
			{
				left++;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		//[begin,keyi-1]keyi[keyi+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

3. 递归到小的子区间时，可以考虑使用插入排序

2.3.2 快速排序非递归

参考代码：

void QuickSortNonR(int* a, int left, int right)
{
   Stack st;
   StackInit(&st);
   StackPush(&st, left);
   StackPush(&st, right);
 
   while (StackEmpty(&st) != 0)
   {
      right = StackTop(&st);
      StackPop(&st);
      left = StackTop(&st);
      StackPop(&st);
 
     if(right - left <= 1)
     continue;
 
     int div = PartSort1(a, left, right);
     // 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
     StackPush(&st, div+1);
     StackPush(&st, right);
 
     StackPush(&st, left);
     StackPush(&st, div);
  }
 
     StackDestroy(&s);
}

#include"Stack.h"

//非递归快速排序
//递归->非递归
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 keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);

			++cur;
		}

		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		//[begin,keyi-1] keyi [keyi+1,end]
		if (keyi < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin + 1 < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

深度太深，递归可能会挂掉，因为栈可能会溢出

递归改非递归的核心是：用栈来存区间

队列也可以处理

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

2.4 归并排序

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

递归参考代码：

//归并排序
void _MergeSort(int* a, int begin,int end,int*tmp)
{
	if (begin == end)
		return;

	int mid = (begin + end) / 2;
	//[begin,mid][mid+1,end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	//归并
	int begin1 = begin,end1 = mid;
	int begin2 = mid + 1,end2 = end;
	int i = begin;
	//依次比较，取小的尾插tmp数组
	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++];
	}

	memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a,0,n-1,tmp);

	free(tmp);
	tmp = NULL;
}

非递归参考代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	 
	while (gap < n)
	{
		printf("%d:->", gap);
		for (int j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = begin1 + gap - 1;
			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
			printf("[%d,%d][%d,%d]",begin1,end1,begin2,end2);

			//越界问题处理
			if (end1 >= n || begin2 >= n)
				break; 

			if (end2 >= n)
				end2 = n - 1;

			int i = j;
			//依次比较，取小的尾插tmp数组
			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++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * (end2-j+1));
		}
		printf("\n");
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

2.5 非比较排序

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

局限：比如浮点数、字符串、结构体之类的都不可以排

负数不是问题

操作步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

参考代码：

//计数排序
//时间复杂度：O(N+range)
//空间复杂度：O(range)
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}

	int range = max - min + 1;
	int* count = malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}

	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. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定

三、排序算法复杂度及稳定性分析

四、选择题练习

总结

在本篇博客中，详细介绍了几种常见的排序算法，并使用C语言进行了实现。这些算法各有优劣，在不同的应用场景下有不同的性能表现。例如，冒泡排序、插入排序和选择排序在处理小规模数据时效率较高，但在大规模数据下可能会表现出较低的效率；而快速排序和归并排序虽然在最坏情况下的时间复杂度较高，但在实际的平均情况下，它们的效率通常优于前者。因此，选择合适的排序算法要根据实际的数据规模和需求来决定。同时，我们还了解了C语言中的指针和数组操作，这对于理解这些排序算法的实现是非常重要的。希望本篇博客能帮助读者更好地理解和掌握排序算法，以及在C语言中的实现方式。

标签：Chapter,right,end,int,gap,排序,left
From： https://blog.csdn.net/m0_74251523/article/details/140656146

文章目录

一、排序的概念及其运用

1.1 排序的概念

1.2排序运用

1.3 常见的排序算法

二、常见排序算法的实现

2.1 插入排序

2.1.1基本思想

2.1.2 直接插入排序

2.1.3 希尔排序(缩小增量排序)

2.2 选择排序

2.2.1基本思想

2.2.2 直接选择排序

2.2.3 堆排序

2.3 交换排序

2.3.1冒泡排序

2.3.2 快速排序

2.3.2 快速排序优化

2.3.2 快速排序非递归

2.4 归并排序

2.5 非比较排序

三、排序算法复杂度及稳定性分析

四、选择题练习

总结

相关文章

赞助商

阅读排行