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

在这里插入图片描述
计数排序也被称为桶排序或者箱排序，都是它和常规的桶排序还是有较为明显的区别，在这篇文章中还是使用计数排序的称呼。计数排序可以进一步将排序的时间复杂度降低到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;
    }
}