1. 找出待排序数组中的最大值和最小值
遍历待排序数组，找出其中的最大值和最小值。

2. 创建计数数组
创建一个新的计数数组，其大小为（最大值 - 最小值 + 1）。
初始化计数数组的所有元素为0。

3. 统计元素出现的次数
再次遍历待排序数组，对于数组中的每个元素，将其值减去最小值（为了使得计数数组的下标从0开始），并将计数数组中对应下标的值加1。

4. 利用计数数组排序
从后向前遍历待排序数组（从大到小是为了保证稳定性，即相同元素在排序后保持原有顺序）。
对于每个元素，将其值减去最小值，然后利用计数数组找到其在排序后数组中的位置，并将该元素放到正确的位置上。
同时，将计数数组中对应位置的值减1，表示该位置已经被占用。

5. 完成排序

实现代码如下


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* tmp = (int*)calloc(max - min +1, sizeof(int));//自动将值其置为0
	for (int i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	int count = n-1;
	for (int i =  max - min; i >=0; i--)
	{
		while (tmp[i]--) 
		{
			a[count--] = i + min;
		}
	}
	free(tmp);
	tmp = NULL;
}

时间复杂度与空间复杂度

1. 时间复杂度

统计元素出现次数的时间复杂度为 O(n)。

根据计数数组进行排序的时间复杂度为 O(n)。

综上所述计数排序的时间复杂度为一般 O(n)。

2. 空间复杂度

由于计数排序需要额外的空间来存储计数数组

所以计数排序的空间复杂度主要取决于计数数组的大小，即 n。因此，计数排序的空间复杂度为 O(n)。

计数排序的特点

计数排序适用于待排序数组中的元素为非负整数(负数不是不能排)，并且元素的取值范围不大于计算机可以表示的最大范围。
如果待排序数组中的元素是负数，或者元素的取值范围较大，计数排序可能不适用，因为它需要额外的空间来存储计数数组。
计数排序是一种稳定的排序算法，即相同元素在排序后保持原有的顺序。

计数排序的时间复杂度为O(n)，其中n是待排序数组的长度

二. 桶排序

概念

桶排序是一种分配式排序算法，它将待排序的数据分到有限数量的桶子里。每个桶子再个别排序（可能使用别的排序算法或以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分布的时候，桶排序使用线性时间（O(n)）

步骤思路如下

1.创建n个桶

2. 将待排序元素分散到各个桶中

3. 对每个桶内的元素排序(可以使用别的排序算法)

4. 读取每个桶的元素，按顺序放回原数组中

实现代码如下


#define BUCKET_SIZE 100
#define MAX_NUM 10
void BucketSort(int arr[], int n) {
	if (n <= 1) {
		return;
	}
 
	int bucket[BUCKET_SIZE][MAX_NUM / BUCKET_SIZE + 1]; // 桶数组，每个桶的大小为MAX_NUM/BUCKET_SIZE+1
	int bucketIndex[BUCKET_SIZE] = { 0 }; // 每个桶的当前元素数量
 
	// 将元素放入对应的桶中
	for (int i = 0; i < n; i++) {
		int index = arr[i] / BUCKET_SIZE; // 计算桶的索引
		bucket[index][bucketIndex[index]++] = arr[i]; // 将元素放入桶中
	}
 
	// 对每个桶进行排序
	for (int i = 0; i < BUCKET_SIZE; i++) {
		if (bucketIndex[i] > 0) {
			InsertSort(bucket[i], bucketIndex[i]); // 使用插入排序对桶内元素进行排序
 
			// 将桶内元素放回原数组
			for (int j = 0; j < bucketIndex[i]; j++) {
				arr[i * (MAX_NUM / BUCKET_SIZE + 1) + j] = bucket[i][j];
			}
		}
	}
}

时间复杂度与空间复杂度

1. 时间复杂度

①最坏情况

若数据的分布非常不均匀，几乎所有的元素都进入一个桶中，那么桶排序时间复杂度为O(N²)

②最好情况

如果数据分布非常均匀，每个桶中元素数量大致相同，并且使用其他排序算法也达到最佳的时间复杂度，那桶排序时间复杂度为O(N)

③平均情况

平均情况下桶排序时间复杂度大概为O(N)

2. 空间复杂度

空间复杂度大概为O(N+M)，其中M为桶的数量，N为开辟数组长度

桶排序的特点

适用于大量数据的排序，是一种高效的排序算法。相比于比较排序算法，桶排序不需要进行元素之间的比较，因此在某些情况下可以更快地完成排序。

是稳定的排序算法，相同元素的相对顺序不会改变。

需要额外的空间来存储桶，如果待排序元素数量较大，可能会占用较多的内存空间。

适用于待排序元素分布均匀的情况。对于分布不均匀的数据，可能导致桶的数量不均衡，影响排序效率。

适用场景
例如在对年龄、成绩等具有一定范围的数据进行排序时。当待排序元素数量较大，且数据分布较为均匀时，桶排序可以提供较高的排序效率。

三. 基数排序

概念

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较，直至完成最高位比较

步骤思路如下

1. 寻找待排序数组中最大的数，并确定其是几位数

2. 创建两个数组，一个二维数组，一个一维数组，进入循环，最高位有多少循环多少次(从1开始，因为没有第0位)

3. (使两个数组元素为0)使用一维数组记录当前位的每个数出现的次数

4. 使用前缀和记录下来<=i数字的数量

5. 从后往前遍历存入数据（从大到小是为了保证稳定性，即相同元素在排序后保持原有顺序）。

6. 通过遍历给原数组赋值

7. 重复 2，3，4，5，6 操作直至结束

实现代码如下


int GetDigit(int x,int i)
{
	int count = x;
	int n = i;
	while (--n>0)
	{
		count /= 10;
	}
	count %= 10;
	return count;
}
void RadixSort(int* a, int n)
{
	int max=a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
	}
	int digit1 = 0;
	while (max)
	{
		max /= 10;
		digit1++;
	}
 
	int bucket[10][20];
 
	int tmp[20] = { 0 };//桶
	for(int i = 1;i<=digit1;i++)
	{
		memset(bucket, 0, sizeof(bucket));
		memset(tmp, 0, sizeof(tmp));
		for (int j = 0; j < n; j++)
		{
			int digit2 = GetDigit(a[j], i);
			tmp[digit2]++;
		}
 
		for (int j = 1; j < 10; j++)//前缀和记录桶中tmp[i]表示小于等于i的数字数量
		{
			tmp[j] += tmp[j - 1];
		}
		for (int j = n - 1; j >= 0; j--)
		{
			int digit2 = GetDigit(a[j],i);
			bucket[digit2][tmp[digit2]--] = a[j];
		}
		int k = 0;
 
		for (int d = 0; d < 10; d++)
		{
			for (int j = 0; j < 20; j++)
			{
				if(bucket[d][j]!=0)
				a[k++] = bucket[d][j];
			}
		}
	}
}

时间复杂度与空间复杂度

1. 时间复杂度

要进行 i(最高位的位数) 趟排序，每趟排序需要将元素分派到k个桶，所以每趟排序的时间复杂度为O(n+k) 走i趟时间复杂度就为O(i(n+k)) 但桶的个数通常是固定的，执行的躺数一般又较小，所以基数排序的时间复杂度趋近于O(n)

2. 空间复杂度

由于开辟了两个数组辅助，假设两个数组长度分别为N，M，所以基数排序的空间复杂度大概为O(N+M)

基数排序的特点

基数排序是一种稳定的排序算法。在排序过程中，相同元素的相对顺序保持不变。这是因为基数排序是按照数字的每一位进行排序的，而相同元素的每一位都是相同的，所以它们的相对顺序不会发生变化。

基数排序是一种非比较型排序算法，它不通过比较元素的大小来进行排序，而是通过分配和收集的方式实现排序。这使得基数排序在某些情况下比基于比较的排序算法（如快速排序、归并排序等）更加高效。

基数排序特别适用于对整数进行排序，尤其是当待排序的整数范围不大，且整数位数相差不大时。在这种情况下，基数排序的效率很高，因为只需要进行有限次的分配和收集操作。

基数排序需要额外的空间来存储桶（或子数组），以便进行元素的分配和收集。如果待排序的元素数量很大，这可能会占用较多的内存空间。因此，在使用基数排序时，需要考虑内存使用情况。

基数排序的时间复杂度可以近似认为是线性的。这使得基数排序在处理大数据集时具有较高的效率。

基数排序不仅适用于数组排序，还适用于链表排序。因为链表在分配和收集元素时不需要移动元素本身，只需要改变节点的指针指向即可。这使得基数排序在链表排序中具有更高的效率。

这篇就到这里啦，感谢支持

(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/870816