首页 > 其他分享 >十大经典排序之计数排序

十大经典排序之计数排序

时间:2024-03-22 18:58:05浏览次数:27  
标签:arr int 计数 数组 经典 sorted 排序

文章目录

概要

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

整体架构流程

(1)找出待排序的数组中最大和最小的元素
(2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项
(3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
(4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print_arr(int *arr, int n) {
        int i;
        printf("%d", arr[0]);
        for (i = 1; i < n; i++)
                printf(" %d", arr[i]);
        printf("\n");
}

void counting_sort(int *ini_arr, int *sorted_arr, int n) {
        int *count_arr = (int *) malloc(sizeof(int) * 100);
        int i, j, k;
        for (k = 0; k < 100; k++)
                count_arr[k] = 0;
        for (i = 0; i < n; i++)
                count_arr[ini_arr[i]]++;
        for (k = 1; k < 100; k++)
                count_arr[k] += count_arr[k - 1];
        for (j = n; j > 0; j--)
                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
        free(count_arr);
}

int main(int argc, char **argv) {
        int n = 10;
        int i;
        int *arr = (int *) malloc(sizeof(int) * n);
        int *sorted_arr = (int *) malloc(sizeof(int) * n);
        srand(time(0));
        for (i = 0; i < n; i++)
                arr[i] = rand() % 100;
        printf("ini_array: ");
        print_arr(arr, n);
        counting_sort(arr, sorted_arr, n);
        printf("sorted_array: ");
        print_arr(sorted_arr, n);
        free(arr);
        free(sorted_arr);
        return 0;
}

小结

计数排序的特征:
当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解,例如有 10 个年龄不同的人,统计出有 8 个人的年龄比 A 小,那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去 1 的原因。

标签:arr,int,计数,数组,经典,sorted,排序
From: https://blog.csdn.net/cui211472325/article/details/136949548

相关文章

  • Java编程经典例题|水仙花数
     一、题目描述水仙花数(NarcissisticNumber)也被称为阿姆斯特朗数(ArmstrongNumber),它是一个n位数,其各位数字的n次方之和等于该数本身。例如,对于三位数的水仙花数,其定义是:一个三位数,它的每个位上的数字的3次幂之和等于它本身。例如,153是一个水仙花数,因为1^3+5^3+3^3=153......
  • Java - 冒泡排序
      //冒泡排序publicclassBubbleSort{ publicstaticvoidmain(String[]args){ //定义一个整型的数组 int[]array={64,34,25,12,22,11,90} bubbleSort(array); for(inti:array){ System.out.println(i+""); } } publicstaticvoidbubbl......
  • SpringBoot3.x与SpringDoc OpenApi之Swagger接口排序
    直接使用Swagger之后,发现所有的Controller接口菜单都是无序的先看一下效果 就是利用了一下SpringDoc提供的接口做了一下自定义排序1.在Controller上加上注解@Tag(name="MenuController",description="1-菜单管理")这里需要注意description属性,在下面的代码里......
  • leetcode148. 排序链表-归并法
    148.排序链表题干给你链表的头结点head,请将其按升序排列并返回排序后的链表。示例1:输入:head=[4,2,1,3]输出:[1,2,3,4]示例2:输入:head=[-1,5,3,4,0]输出:[-1,0,3,4,5]示例3:输入:head=[]输出:[]提示:链表中节点的数目在范围[0,5*104]内-105<=N......
  • LeetCodeHot100 二分查找 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查
    35.搜索插入位置https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-likedpublicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<......
  • proteus+keil5仿真学习笔记(第二章 1位数码管计数器)
    第二章1位数码管计数器目录第二章1位数码管计数器前言一、数码管的结构原理二、按键应用三、中断处理四、程序设计及仿真proteus电路程序总结前言主要介绍数码管、按键的应用,并涉及单片机中断处理技术。一、数码管的结构原理数码管结构如下:有两种数码......
  • proteus+keil5仿真学习笔记(第三章 4位数码管计数器)
    第三章4位数码管计数器前言一、多位数码管显示程序二、定时器原理三、程序设计与仿真proteus电路程序总结前言4位数码管计数器与1位数码管计数器相比,增加了片选电路,以确定选择哪个数码管进行工作。单片机定时器的应用也与中断处理相似,需要设置一些规定的寄存器,以......
  • 基于EP4CE6F17C8的FPGA单数码管秒计数实例
    一、电路模块本例的电路模块与“基于EP4CE6F17C8的FPGA数码管动态显示实例”中的完全一样,此处就不再给出了。二、实验代码本例实现1个数码管循环显示字符1~F,显示间隔为1秒,代码使用Verilog编写,采用例化的形式,共有三个文件。先编写数码管实现显示字形解码的程序,模块名称为seg_de......
  • 冒泡排序和选择排序--C语言
    冒泡排序(升序):设计思想:每两个相邻的数进行比较,大的往后走详细过程:例:99,100,88,80,100,90,77,22,33,90第一遍:99与100比较,100大,继续向后走,100与88比较,100大,100与88交换一下位置,继续向后走100与80比较,100大,100与80交换一下位置,继续向后走100与100比较,相等,不需要......
  • 合并两个排序的链表
    合并两个排序的列表题目描述输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。数据范围链表长度[0,500][0,500]。样例输入:1->3->5,2->4->5输出:1->2->3->4->5->5代码实现迭代版本structListNode{intval;ListNode*nex......