C2. 09 数组排序的专项练习(二)

课堂内容：计数排序的应用

• 计数排序_基本原理

计数排序是一种非比较排序算法，其核心思想是将序列中的元素作为键存储在额外的数组空间中，而该元素的个数作为值存储在数组空间中，通过遍历该数组进行排序。

• 计数排序_参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	 // 定义一个大小为 100005 的整型数组 a ，并初始化为 0 。这个数组用于记录每个整数出现的次数  
    int a[100005]={0};
	// 声明变量 n（表示整数数量），m（用于临时存储输入的整数）和 max1（用于记录输入中的最大整数）  
    int n, m, max1=0;  
  
    cin>>n; // 从标准输入读取整数 n
  
    for(int i=1;i<=n;i++) // 循环 n 次，每次读取一个整数  
    {  
        cin>>m;          // 读取整数 m
        max1=max(max1,m); // 更新 max1 为 max1 和 m 中的较大值  
        a[m]++;           // 将整数 m 在数组 a 中的对应位置加 1
    }  
  
    for(int i=0;i<=max1;i++) // 循环从 0 到 max1，遍历数组 a  
    {  
        while(a[i])       // 如果整数 i 出现过（即 a[i] 大于 0 ）  
        {  
            cout<<i<<" ";  // 输出整数 i
            a[i]--;        // 将整数 i 在数组 a 中的计数减 1 ，表示已经输出了一次  
        }  
    }  
    return 0;
}

• 计数排序_代码解析

• 首先，找出待排序的数组中最大和最小的元素。
• 然后，创建一个新的计数数组，其大小为最大值与最小值的差加1。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
• 对计数数组进行累加操作，使每个索引的值变为小于或等于该索引的元素的个数。
• 反向遍历待排序数组，对于每个元素，根据其在计数数组中的值确定其在排序后数组中的位置，并将其放到正确的位置上。