C++ 计数排序实例详解

简介

计数排序是一种稳定的排序算法，其时间复杂度为O(n + k)，其中n为待排序序列的长度，k为序列中元素的取值范围。相比其他排序算法，计数排序的时间复杂度较小，但需要占用更多的内存空间。计数排序在排序的元素值比较小，且元素集合密集程度比较大的场景下表现更加出色。

算法原理

计数排序的基本思想是，统计待排序序列中，每个元素出现的个数，并将其记录在计数数组中。然后，根据计数数组中统计到的元素出现个数，依次重构有序序列。

具体过程如下：
1. 统计待排序序列元素的个数，将其存放在计数数组中（计数数组大小为待排序序列中元素的取值范围）。
2. 计算计数数组中的累加和，用于计算每个元素在有序序列中的位置。
3. 依次遍历待排序序列，将每个元素根据其在计数数组中所对应的位置，依次放入有序序列中，并将其对应的计数数组位置上的元素值减1。

C++代码实现

#include <iostream>
#include <cstring>

using namespace std;

void CountingSort(int arr[], int n)
{
    int k = arr[0];
    for(int i = 1; i < n; i++)
    {
        if(k < arr[i])
        {
            k = arr[i];
        }
    }

    int* count = new int[k + 1];
    memset(count, 0, sizeof(int) * (k + 1));

    for(int i = 0; i < n; i++)
    {
        count[arr[i]]++;
    }

    for(int i = 1; i <= k; i++)
    {
        count[i] += count[i - 1];
    }

    int* sorted = new int[n];
    for(int i = n - 1; i >= 0; i--)
    {
        sorted[--count[arr[i]]] = arr[i];
    }

    for(int i = 0; i < n; i++)
    {
        arr[i] = sorted[i];
    }

    delete[] count;
    delete[] sorted;
}

int main()
{
    int arr1[] = {3, 4, 1, 7, 6, 5, 8, 9, 2, 10};
    int n1 = sizeof(arr1) / sizeof(int);
    CountingSort(arr1, n1);
    for(int i = 0; i < n1; i++)
    {
        cout << arr1[i] << " ";
    }
    cout << endl;

    int arr2[] = {5, 3, 7, 2, 8, 4, 9, 1, 6};
    int n2 = sizeof(arr2) / sizeof(int);
    CountingSort(arr2, n2);
    for(int i = 0; i < n2; i++)
    {
        cout << arr2[i] << " ";
    }
    cout << endl;

    return 0;
}

示例说明

示例一

输入：

int arr1[] = {3, 4, 1, 7, 6, 5, 8, 9, 2, 10};
int n1 = sizeof(arr1) / sizeof(int);
CountingSort(arr1, n1);

输出：

1 2 3 4 5 6 7 8 9 10

示例二

输入：

int arr2[] = {5, 3, 7, 2, 8, 4, 9, 1, 6};
int n2 = sizeof(arr2) / sizeof(int);
CountingSort(arr2, n2);

输出：

1 2 3 4 5 6 7 8 9

以上两个示例分别演示了计数排序的过程，验证了该算法的正确性。