计数排序

计数排序是一种稳定的线性时间排序算法，计数排序不是比较排序，排序的速度快于任何比较排序算法，计数排序可以配合基数排序，能够更有效排序数据范围很大的数组

一、计数排序步骤

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

二、计数排序实现

#include "utili.h"

//假设要排序的数字都是小于100的
void count_sort( int data[], int size )
{
    int count_arr[100];
    int temp[size];
    int i, j, k;
    for ( k = 0; k < 100; k++ )
        count_arr[k] = 0;
    for ( i = 0; i < size; i++ )
        count_arr[data[i]]++;
    for ( i = 1; i < 100; i++ )
        count_arr[i] = count_arr[i-1] + count_arr[i];
    for ( j = size; j > 0; j-- )
    {
        temp[--count_arr[data[j-1]]] = data[j-1];
    }
    for ( i = 0; i < size; ++i )
        data[i] = temp[i];
}

<>

三、性能分析

• 时间复杂度：O(N+k)
• 空间复杂度：O(N+k)
• 稳定性：稳定