前言

一种将无序数组进行排序的方法。

计数排序，wiki参考：
https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F

计数排序，主要思想：

1. 引入临时数组。
2. 对于元素i，计算出比i小的数，从而确定i的位置。
3. 计算i的重复，填充数组。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>

// 计数排序，
// 1. 引入临时数组。
// 2. 对于元素i，计算出比i小的数，从而确定i的位置。
// 3. 计算i的重复，填充数组。 


void count_sort_normal(int source_array[], int source_array_length)
{
    int i, j, k;

    // 定义临时数组，并且初始值为0
    int* tmp_group = (int*)calloc(sizeof(int) * source_array_length);

    // 目标元素在有序数组中的索引
    int target_index;

    // 目标元素的重复数
    int target_num;

    for (i = 0; i < source_array_length; i++)
    {
        target_index = 0;
        target_num = 0;

        for (j = 0; j < source_array_length; j++)
        {
            // 遍历得出目标元素的索引
            if (source_array[j] < source_array[i])
            {
                target_index++;
            }
            else
            {
                // 计算重复数
                if (source_array[j] == source_array[i])
                {
                    target_num++;
                }
            }
        }
        // 对临时数组填充。当临时数组中的值为0时，说明未填充。当前元素为0时，无需填充。
        if (tmp_group[target_index] == 0 && source_array[i] !=0 )
        {
            // 根据重复数填充
            for (k = 1; k <= target_num; k++)
            {
                tmp_group[target_index] = source_array[i];
                target_index++;
            }
        }
    }


    // 将原数组替换
    for (i = 0; i < source_array_length; i++)
    {
        source_array[i] = tmp_group[i];
    }
}


int main()
{
    // 生成随机测试列表
    int test_list[20];
    int test_list_length = sizeof(test_list) / sizeof(int);

    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 普通计数排序
    count_sort_normal(test_list, test_list_length);
    printf("普通计数排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    return 0;
}

执行结果参考：

image.png