计数，桶与基数排序

 

目录

 

一. 计数排序

概念

 步骤思路如下

 实现代码如下

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

计数排序的特点

二. 桶排序

概念 

 步骤思路如下

实现代码如下 

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

桶排序的特点

 三. 基数排序

概念

步骤思路如下

实现代码如下

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

基数排序的特点

---

一. 计数排序

概念

计数排序是一种非比较排序算法，它的基本思想是利用数组下标的有序性，将元素作为计数数组的相应下标，并在该下标位置存储相应的元素数量，最后根据计数数组填充待排序数组

 步骤思路如下

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));//自动将值其置为0for (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+1int 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ᵒᵛᵉᵧₒᵤ❤