c++计数排序（c++十个数排序）

计数排序是一种非比较排序算法，用于对一组数据进行排序。它的基本思想是通过统计每个元素出现的次数，然后依次输出排序结果。

## 算法原理

计数排序的核心是构建一个辅助数组count，数组长度为待排序数组中元素的最大值加一。然后遍历待排序数组，将每个元素出现的次数记录在count数组对应位置上。最后遍历count数组，根据元素出现的次数，将元素依次输出到结果数组中。

## 算法步骤

1. 找出待排序数组中的最大值max。

2. 创建一个长度为max+1的辅助数组count，并将所有元素初始化为0。

3. 遍历待排序数组，对每个元素在count数组对应位置上进行计数。

4. 根据count数组中的计数信息，依次输出元素到结果数组中。

5. 返回结果数组作为排序结果。

## 算法分析

计数排序是一种稳定的线性时间复杂度排序算法，时间复杂度为O(n)，其中n为待排序数组的长度。由于需要创建辅助数组count，所以空间复杂度为O(k)，其中k为待排序数组中元素的最大值。计数排序适用于非负整数类型的数据排序，当待排序数据范围不大时，计数排序的效率较高。

## 示例代码

```c

void countingSort(int arr[], int n) {

int max = arr[0];

for (int i = 1; i < n; i++) {

if (arr[i] > max) {

max = arr[i];

}

}

int count[max + 1];

for (int i = 0; i <= max; i++) {

count[i] = 0;

}

for (int i = 0; i < n; i++) {

count[arr[i]]++;

}

int index = 0;

for (int i = 0; i <= max; i++) {

while (count[i] > 0) {

arr[index++] = i;

count[i]--;

}

}

```

以上是计数排序的实现代码，可以将此代码直接运行来对一个整数数组进行排序。

## 总结

计数排序是一种非比较排序算法，适用于非负整数类型的数据排序。它的核心思想是通过统计每个元素出现的次数，然后依次输出排序结果。计数排序的时间复杂度为O(n)，空间复杂度为O(k)，效率较高。同时，计数排序是一种稳定的排序算法，保证相等元素的前后顺序不变。