美文网首页
C语言:十种排序(八) - 计数排序

C语言:十种排序(八) - 计数排序

作者: lzp1234 | 来源:发表于2019-08-12 15:31 被阅读0次

前言

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

计数排序,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

相关文章

  • C语言:十种排序(八) - 计数排序

    前言 一种将无序数组进行排序的方法。 计数排序,wiki参考:https://zh.wikipedia.org/w...

  • 常见十大排序算法概述

    排序算法概述 网上常见的排序算法有十种:冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排...

  • C语言——计数排序

    待排序的数组A 从数组中取出最大值k 新建一个数组B,用于存储排序的输出 新建一个数组C,C.length = k...

  • 排序算法Java实现

    本文会通过Java语言实现:冒泡排序,插入排序,选择排序,归并排序,快速排序,桶排序,计数排序,基数排序,希尔排序...

  • 有关iOS基础知识总结

    1.C语言 排序算法)(数组的大小排序,字母的先后排序,单词的计数) 2.面向过程和面向对象 面向过程:分析出解决...

  • 基本排序算法的Python实现

    本篇主要实现九(八)大排序算法,分别是冒泡排序,插入排序,选择排序,希尔排序,归并排序,快速排序,堆排序,计数排序...

  • 哈希&计数排序和桶排序&基数排序

    length在大部分语言里是最大的数字下标+1 完整的计数排序 桶排序 桶排序是计数排序的升级版排序,要么浪费时间...

  • 常用排序算法总结9一一计数排序

    定义 计数排序(英语:Counting Sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C,其中...

  • 十大排序算法动画

    目录一、冒泡排序二、选择排序三、插入排序四、希尔排序五、归并排序六、快速排序七、堆排序八、计数排序九、桶排序十、基...

  • 十大排序算法(JS)

    目录一、冒泡排序二、选择排序三、插入排序四、希尔排序五、归并排序六、快速排序七、堆排序八、计数排序九、桶排序十、基...

网友评论

      本文标题:C语言:十种排序(八) - 计数排序

      本文链接:https://www.haomeiwen.com/subject/lzeujctx.html