数据结构——计数、桶、基数排序

目录

引言

计数排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

桶排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

基数排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

排序算法的稳定性

1.稳定性的概念

2.各个排序算法的稳定性

结束语

引言

目前写的排序：

数据结构——冒泡、选择、插入和希尔排序

数据结构——快速排序

数据结构——归并排序

数据结构——堆排序

有需要的可以看看。

我们接下来学习一下计数排序、桶排序、基数排序。

计数排序

计数排序（Counting Sort）是一种非基于比较的排序算法，由Harold H. Seward在1954年提出。该算法的主要优势在于其线性时间复杂度，特别适用于待排序元素为整数且范围较小的情况。

1.算法思想

计数排序的基本思想是统计数组中每个元素的出现次数，然后利用这些信息将原始序列重新组合成有序序列。它并不直接比较元素之间的大小，而是通过计算小于等于某个值的元素个数来确定该元素在排序后数组中的位置。

2.算法步骤

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

2.创建计数数组：计数数组的长度通常设置为待排序数组中的最大值加1（如果已知范围，则可以直接设定长度为范围大小）。计数数组的初始值全部设为0。

3.统计元素出现次数：遍历待排序数组，对于数组中的每个元素，在计数数组对应下标的位置上加1，以统计该元素的出现次数。

4.修改计数数组：对计数数组进行前缀和操作，即每个位置的值变为它本身加上前一个位置的值。这样，计数数组的每个位置就代表了小于等于该下标值的元素在排序后数组中的最后位置。

5.重建输出数组：从后向前遍历待排序数组，根据计数数组中的值确定当前元素在输出数组中的位置，并更新计数数组。具体地，对于待排序数组中的每个元素，找到计数数组中对应下标的值（即该元素在排序后数组中的位置），将元素放到输出数组的相应位置，并将计数数组中对应下标的值减1。

6.输出排序后的数组：此时，输出数组就是排序后的数组。

动图演示如下：

3.代码实现

void CountSort(int* arr, int n)
{
    // 初始化最小值和最大值为数组的第一个元素  
    int min = arr[0];
    int max = arr[0];

    // 遍历数组，找到最小值和最大值  
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < min)
            min = arr[i]; // 更新最小值  
        if (arr[i] > max)
            max = arr[i]; // 更新最大值  
    }

    // 计算值的范围（即最大值和最小值之间的差值加1）  
    int range = max - min + 1;

    int* count = (int*)calloc(range, sizeof(int));
    if (count == NULL)
    {
        perror("calloc fail:");
        return;
    }

    // 统计每个元素的出现次数  
    // 通过数组下标转换（arr[i] - min）将原始数组的值
    // 映射到计数数组的索引上  
    for (int i = 0; i < n; i++)
    {
        count[arr[i] - min]++;
    }

    // 根据计数数组中的计数，重建排序后的数组  
    // 遍历计数数组，每次将对应计数值数量的元素放到arr中  
    int index = 0; 
    for (int i = 0; i < range; i++)
    {
        // 当count[i]大于0时，说明有i+min这个值的元素需要被放置  
        while (count[i]--)
        {
            arr[index++] = i + min; // 放置元素，并更新index  
        }
    }

    free(count);
    count = NULL; 
}

测试一下：

4.复杂度分析

时间复杂度：由于遍历了原数组与range数组，因此时间复杂度为O(n+range)。

空间复杂度：开辟了大小为range的数组，所以空间复杂度为O(range)。

桶排序

桶排序（Bucket Sort）是一种基于分配策略的排序算法。

1.算法思想

桶排序的算法思想是将数组中的元素分配到有限数量的桶（或称为箱）里，每个桶再分别进行排序（可能使用其他排序算法或递归使用桶排序），最后合并成结果序列。

2.算法步骤

1.初始化桶：首先，需要确定桶的数量及每个桶对应的数据范围。这通常与待排序数据的范围有关，目的是使每个桶尽可能均匀地包含一部分数据。

2.分配元素：遍历待排序序列，将每个元素根据其值放入对应的桶中。这一步相当于对数据进行初步的划分和聚集。

3.桶内排序：对每个非空桶内部使用其他排序算法（如插入排序、快速排序等）进行排序，确保每个桶内的数据有序。

4.合并桶：按照桶的顺序，依次从每个桶中取出元素，合并成一个有序序列，即完成整个数据集的排序。

动图演示：

PS：这里的位数桶只是方便演示。

3.代码实现

桶内的排序我们同样可以借助插入排序来实现。

代码如下：

#define BUCKET_SIZE 10  // 定义桶的数量  
#define ARRAY_SIZE 30   // 定义数组的大小  

void InsertSort(int* arr, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0)
        {
            if (tmp < arr[end])
            {
                arr[end + 1] = arr[end];
                --end;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

// 桶排序函数  
void bucketSort(int arr[], int n) 
{
    int bucket[BUCKET_SIZE][ARRAY_SIZE], max = arr[0], min = arr[0];
    int i, j, k;
    int b_size[BUCKET_SIZE] = { 0 }; // 每个桶的元素数量  

    // 找到数组中的最大值和最小值  
    for (i = 1; i < n; i++) 
    {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }

    // 计算桶的间隔  
    int range = max - min;
    int interval = range / BUCKET_SIZE; 

    // 将数据分配到各个桶中  
    for (i = 0; i < n; i++) 
    {
        int bi = (arr[i] - min) / interval; // 使用整数除法来分配桶  
        if (bi >= BUCKET_SIZE)
        {
            bi = BUCKET_SIZE - 1;
        }
        bucket[bi][b_size[bi]++] = arr[i];
    }

    // 对每个桶进行排序  
    for (i = 0; i < BUCKET_SIZE; i++)
    {
        InsertSort(bucket[i], b_size[i]);
    }

    // 合并桶中的数据  
    k = 0;
    for (i = 0; i < BUCKET_SIZE; i++)
    {
        for (j = 0; j < b_size[i]; j++)
        {
            arr[k++] = bucket[i][j];
        }
    }
}

测试一下：

4.复杂度分析

时间复杂度：

(1)如果数据均匀分布在桶中，且每个桶内能快速排序（如计数排序、插入排序等），则平均时间复杂度可以达到O(n + k)，其中n是元素总数，k是桶的数量。这是因为在理想情况下，每个桶只需要处理少量元素。

(2)当输入数据已经完全有序或者极度集中在一个桶内，桶排序会退化为线性查找，此时时间复杂度为O(n^2)。

空间复杂度：由于需要额外存储每个桶以及额外的空间用于最终结果的合并，因此空间复杂度通常是O(n + k)。

基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，它通过键值的各个位的值，将要排序的元素分配到某些“桶”中，以达到排序的目的。基数排序也被称为“分配式排序”或“桶子法”（bucket sort），是桶排序的扩展。

1.算法思想

基数排序的基本原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体来说，它首先将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

2.算法步骤

1.计算最大数位数：首先找出待排序数组中最大数的位数。

2.统一数位长度：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。

3.按位排序：从最低位开始，依次进行一次排序。排序时，根据当前位的数值，将元素分配到对应的桶中。

4.合并桶中元素：将各个桶中的元素依次取出，合并成一个新的有序数组。

5.重复步骤3和4：对更高位进行排序，直到最高位排序完成。

3.代码实现

// 获取数字num在exp位上的数字
int Get_digit(int num, int exp) 
{
    return (num / exp) % 10;
}

// 对数组arr中的数字按exp位进行计数排序
void CountSortDigit(int* arr, int n, int exp) 
{
    // 分配一个大小为10的数组来计数0-9每个数字出现的次数
    int* counter = (int*)malloc(sizeof(int) * 10);
    if (counter == NULL) 
    {
        perror("malloc fail:");
        return;
    }
    // 初始化计数器数组
    memset(counter, 0, sizeof(int) * 10);
    // 遍历数组，计算每个数字在exp位上出现的次数
    for (int i = 0; i < n; i++) 
    {
        int x = Get_digit(arr[i], exp);
        counter[x]++;  
    }
    // 累积计数，使counter[i]包含小于或等于i的数字的总数
    for (int i = 1; i < 10; i++) 
    {
        counter[i] += counter[i - 1];
    }
    // 分配一个与原始数组相同大小的临时数组来存储排序后的结果
    int* ret = (int*)malloc(sizeof(int) * n);  
    if (ret == NULL) 
    {
        perror("malloc fail:");
        return;
    }
    // 从后往前遍历原始数组，根据exp位上的数字将元素放入ret数组的适当位置
    for (int i = n - 1; i >= 0; i--) 
    {
        int d = Get_digit(arr[i], exp);
        ret[counter[d] - 1] = arr[i];  
        counter[d]--;
    }
    // 将排序后的结果复制回原始数组
    for (int i = 0; i < n; i++) 
    {
        arr[i] = ret[i];
    }
    free(ret);  
    free(counter);  
}

void RadixSort(int* arr, int n) 
{
    // 找到数组中的最大值，以确定最大的位数
    int max = arr[0];
    for (int i = 1; i < n; i++) 
    {  
        if (arr[i] > max) 
        {
            max = arr[i];
        }
    }
    // 从个位开始，逐步向高位进行排序  
    // exp是当前的位数（1代表个位，10代表十位，依此类推）
    for (int exp = 1; max / exp > 0; exp *= 10) 
    {
        // 对当前位数进行计数排序
        CountSortDigit(arr, n, exp);
    }
}

测试一下：

4.复杂度分析

时间复杂度：数据量为N、数据为D进制、最大位数为K。时间复杂度可以表示为O((N + D) * K)。但在实际应用中，由于D和K都相对较小，我们通常会将其简化为O(N * K)，并进一步简化为O(N)。

空间复杂度：由于基数排序需要借助长度为N和D的统计数组，因此基数排序空间复杂度为O(N+D)。

排序算法的稳定性

1.稳定性的概念

排序算法的稳定性是指算法在排序过程中，对于具有相同关键字的元素，能否保持它们在原序列中的相对顺序不变。如果保持不变，则称该排序算法是稳定的；如果相对顺序可能发生变化，则称该排序算法是不稳定的。

2.各个排序算法的稳定性

结束语

排序这部分大概就学到这里。

求点赞收藏评论关注！！！

感谢各位大佬的支持！！！