数据结构与算法（经典排序）----计数排序

基本思想： 1、首先遍历待排序数组a，找出待排序数组的最大最小值 2、遍历a数组，将其值放在book数组的下标中，并使用book数组计数 3、累加book数组，计算出前缀和 4、反向遍历数组a，以保证稳定性，并将排好序的值放在b数组中 代码： # include <iostream> # include <algorithm> # include <ctime> # include <cstdlib> # include <numeric> using namespace std; int a[100],b[100],book[1000]; void count_sort(int n){ int max=0,min=9999; // 找到待排序数组的最小、最大值 for(int i=1;i<=n;i++){ if(a[i]>=max){ max=a[i]; } if(a[i]<=min){ min=a[i]; } } // t为book数组的长度 int t=max-min; for(int i=1;i<=n;i++){ // 使用book数组计数 book[a[i]-min]++; } // for(int i=0;i<=t;i++){ // printf("book1:"); // printf("%d--%d ",i,book[i]); // } // printf("\n"); // 累加book数组，计算前缀和 for(int i=1;i<=t;i++){ book[i]=book[i]+book[i-1]; } // for(int i=0;i<=t;i++){ // printf("book2:"); // printf("%d--%d ",i,book[i]); // } // printf("\n"); // 反向遍历a数组，保证稳定性，并将排好序的值放在b数组中 for(int i=n;i>=1;i--){ int x=book[a[i]-min]; b[x-1]=a[i]; book[a[i]-min]--; } // 打印排好序的值 for(int i=0;i<n;i++){ printf("%d ",b[i]); } printf("\n"); } int main(void) { int n; scanf("%d",&n); srand(unsigned(time(NULL))); for(int i=1;i<=n;i++){ a[i]=rand()%100+1; printf("%d ",a[i]); } printf("\n"); count_sort(n); }