编辑代码

#include<iostream>
#include <stdio.h>
using namespace std;
#define N 7       //待排序序列中的元素个数
#define MAX 100   //待排序序列中的最大值不能超过 100
//找到数组中的最大值
int getMax(int list[]) {
    int i, max = list[0];
    for (i = 1; i < N; i++) {
        if (list[i] > max)
            max = list[i];
    }
    return max;
}

void countingSort(int list[]) {
    int i;
    //第 1 步，找到序列中的最大值
    int max = getMax(list);
    //第 2 步，创建一个数组，长度至少为 max+1，并初始化为 0
    int array[MAX] = { 0 };
    int output[N] = { 0 };
    //第 3 步，统计各个元素的出现次数，并存储在相应的位置上
    for (i = 0; i < N; i++) {
        array[list[i]]++;
    }
    //第 4 步，累加 array 数组中的出现次数
    for (i = 1; i <= max; i++) {
        array[i] += array[i - 1];
    }

    //第 5 步，根据 array 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
    for (i = N - 1; i >= 0; i--) {
        output[array[list[i]] - 1] = list[i];
        //第 6 步，数组相应位置上的值减1
        array[list[i]]--;
    }

    // 将 output 数组中的数据原封不动地拷贝到 list 数组中
    for (i = 0; i < N; i++) {
        list[i] = output[i];
    }
}

void printlist(int list[]) {
    int i;
    for (i = 0; i < N; ++i) {
        printf("%d ", list[i]);
    }
}

int main() {
    int list[] = {2,5,3,0,3,0,3};
    //进行计数排序
    countingSort(list);
    printlist(list);
}