排序算法系列之计数排序

计数排序

1 基本原理

1 核心思想：计数排序是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 C ，其中第i个元素是待排序数组 A中值等于 i的元素的个数。然后根据数组 C 来将 A中的元素排到正确的位置。
2 算法分析：
- 找出待排序的数组中最大和最小的元素。确定数组大小C[max-min+1]。
- 统计数组中每个值为 i的元素出现的次数，存入数组 C 的第 i项。
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）。
- 反向填充目标数组：将每个元素 i放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去1

2 实例说明

如上图所示，以一组数据{2，5，3，1，2，3，1，3} 为例，进行计数排序的算法演示：

1. 扫描数组获取最小值 1 和最大值5，新建数组C[6]={0,1,2,3,4,5}。
2. 依次给C[i]赋值，1的次数为2，故C[1]=2;3的次数为3,所以C[3]=3;如此完成数组C的赋值。
3. 更新C[i]的值，依次和前一个元素累加，新值等于i在序列中的排列位置。
4. 根据位置，依次输出i,完成排序。

3 代码实现

// 计数排序（C++）
void CountSort(vector<int> &a)
{
    int min = a[0];
    int max = a[0];

    for (int i = 0; i<a.size(); i++)
    {
        if (a[i]<min)
        {
            min = a[i];
            continue;
        }
        if (a[i]>max)
        {
            max = a[i];
        }
    }

    vector<int> B(a.size());
    vector<int> C(max - min +1);

    for (int i = 0; i<a.size(); i++)
    {
        C[a[i] - min]++;
    }

    //原版计数排序
    for(int index = 1; index < C.size(); index++)
    {
        C[index] = C[index] + C[index - 1];
    }
    for(int index = a.size() - 1; index > -1; index--)
    {
        B[C[a[index] - min] - 1] = a[index];
        C[a[index] - min]--;
    }
    for(int index = 0; index < a.size(); index++)
    {
        a[index] = B[index];
    }

    //空间优化版计数排序(替换原版部分代码)

    int n = 0;
    for (int i = 0; i<C.size(); i++)
    {
        for (int count = 0; count<C[i]; count++)
        {
            a[n++] = i + min;
        }
    }
}

4 性能分析

• 1 时间复杂度：
  当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。故时间复杂度为O(N)。
• 2 空间复杂度：
  排序过程中，需要一个辅助空间，因此空间复杂度为O(n)。
• 3 算法稳定性：
  选择排序是稳定的算法。