算法基础：排序算法：计数排序

缺乏、安全感 2022-12-18 13:57 201阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
计数排序也被称为桶排序或者箱排序，都是它和常规的桶排序还是有较为明显的区别，在这篇文章中还是使用计数排序的称呼。计数排序可以进一步将排序的时间复杂度降低到O(n)，而且也可以是稳定的排序，理解起来也很容易，实现简单。它算是空间换时间策略的代表之一，空间消耗过大，受排序序列的影响极大，能够排序的场合受限，这些也都是计数排序的阿喀琉斯之踵（或许类比失当，计数排序也很难称得上是排序之中的阿喀琉斯）。

### 目录 ###

*  算法思路
 *  算法要点
 *  模拟实现
 *  结果验证
 *  算法限制

--------------------

# 算法思路 #

>  *  计数排序在理解上大概是比冒泡排序还要简单的排序，它的做法就是根据待排序的内容生成一大块连续的空间，能够保存待排序的最大值-最小值的范围，然后巧妙的将值作为下标进行保存，而该下标的元素中保持记录重复的次数，然后输出的时候根据顺序进行输出，有计数值的按照计数值进行输出即可，有重复的根据计数值进行递减。

--------------------

# 算法要点 #

简单的计数排序模拟几乎没有什么要点：

*  额外空间：预备一个大的空间，能将输入的范围都保存进去
 *  循环计数：对于待排序的元素进行循环，将带排序的元素的值作为下标，在额外空间的数组中进行计数
 *  结果输出：对额外空间的数组进行循环，有计数值的递减输出即可。

# 模拟实现 #

void count_sort(int* arr, int num, int* count) { 
        for (int i=0; i<num; i++) { 
            count[arr[i]]++;
        }
    }

--------------------

# 结果验证 #

加上打印和调用的示例代码，可以使用如下方式进行验证

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define MAX_ARRAY_LENGTH 10000
    
    void count_sort(int* arr, int num, int* count) { 
        for (int i=0; i<num; i++) { 
            count[arr[i]]++;
        }
    }
    
    void print_array(int* count) { 
        for (int i=0; i<MAX_ARRAY_LENGTH; i++) { 
            for (int j=count[i]; j>0; j--) { 
                printf("%d ",i);
            }
        }
        printf("\n");
    }
    
    int main() { 
        int n = 0;
    
        while (scanf("%d",&n) != EOF) { 
            int count[MAX_ARRAY_LENGTH] = {  0 };
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) { 
                scanf("%d",&array[i]);
            }
            count_sort(array,n,count);
            print_array(count);
            free(array); array= NULL;
        }
    }

执行结果示例

9
    9 8 7 6 5 4 3 2 1
    1 2 3 4 5 6 7 8 9

注：此处算法的稳定性并未得到实现，算法本身是能够实现稳定性的，实际上为了保证稳定性，应该倒序出数或者引入新的空间，但是此处只是模拟排序的介绍，并未做过多延伸。

# 算法限制 #

计数排序在有限的范围内使用效果较好，但是很明显的有如下限制：

*  因为利用连续空间，可能造成极大浪费空间而且范围受限，比如上述例子只能排序10000之内的正整数
 *  直接不作处理的话无法排序小数和负数
 *  受数据影响非常之大，比如1000万个1-100的数字排序，效果会非常好，但是极端来看1 1000000000的两个序列的排序，效率会非常之差

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/1eef07a056724571ac94a68b8ee2c3f3.png