计数排序

综述

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中.
作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数.

算法描述

1.找出待排序的数组中最大和最小的元素；
2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项；
3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加）；
4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1.

示意图

计数排序动态示意图 计数排序静态示意图

性质

排序类别:非交换排序
是否是稳定排序:稳定
是否是原地排序:否
时间复杂度:O(n+k)
空间复杂度:O(k)

---

说明

它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法.
当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序
基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序

计数排序是一个稳定的排序算法.
当输入的元素是n个0到k之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法.
当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法.
计数排序的缺点是当最大值最小值差距过大时,不适用计数排序,当元素不是整数值,不适用计数排序.

算法思想

计数排序对输入的数据有附加的限制条件:
1、输入的线性表的元素属于有限偏序集S；
2、设输入的线性表的长度为n,|S|=k(表示集合S中元素的总数目为k）,则k=O(n).
在这两个条件下,计数排序的复杂性为O(n).

计数排序的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定）.一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上.例如,如果输入序列中只有17个元素的值小于x的值,则x可以直接存放在输出序列的第18个位置上.当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,因此,上述方案还要作适当的修改.

算法过程

假设输入的线性表L的长度为n,L=L1,L2,..,Ln；线性表的元素属于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk}；则计数排序可以描述如下:
1、扫描整个集合S,对每一个Si∈S,找到在线性表L中小于等于Si的元素的个数T(Si)；
2、扫描整个线性表L,对L中的每一个元素Li,将Li放在输出线性表的第T(Li)个位置上,并将T(Li)减1.

Python实现

def count_sort1(array):
    length = len(array)
    res = [None] * length
    # 首次循环遍历, 每个列表的数都统计
    for index in range(length):
        # p 表示 a[i] 大于列表其他数 的次数
        p = 0
        # q 表示 等于 a[i] 的次数
        q = 0
        # 二次循环遍历, 列表中的每个数都和首次循环的数比较
        for two_index in range(length):
            if array[index] > array[two_index]:
                p += 1
            elif array[index] == array[two_index]:
                q += 1
        for k in range(p, p + q):  # q表示相等的次数,就表示, 从p开始索引后, 连续q次,都是同样的数
            res[k] = array[index]
    return res

dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = count_sort1(dest)
print('最后的结果是:', result)

'''
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


void CountSort(int *arr, int len){
    if(arr == NULL) return;
    int max = arr[0], min = arr[0];
    for(int i = 1; i < len; i++){
        if(arr[i] > max)    max = arr[i];
        if(arr[i] < min)    min = arr[i];
    }
    int size = max - min + 1;
    int *count =(int*)malloc(sizeof(int)*size);
    memset(count, 0, sizeof(int)*size);

    for(int i = 0; i < len; i++)
        count[arr[i] - min]++;//包含了自己！
    for(int i = 1; i < size; i++)
        count[i] += count[i - 1];

    int* psort =(int*)malloc(sizeof(int)*len);
    memset(psort, 0, sizeof(int)*len);

    for(int i = len - 1; i >= 0; i--){
        count[arr[i] - min]--;//要先把自己减去
        psort[count[arr[i] - min]] = arr[i];
    }

    for(int i = 0; i < len; i++){
        arr[i] = psort[i];
    }

    free(count);
    free(psort);
    count = NULL;
    psort = NULL;
}


void print_array(int *arr, int len)
{
    for(int i=0; i<len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[8] = {5, 2, 7, 4, 8, 1, 6, 3};
    CountSort(arr, 8);
    print_array(arr, 8);

    return 0;
}