读书笔记-《数据结构与算法》-摘要9[计数排序]

发布时间：2024年01月19日

计数排序，顾名思义，就是对待排序数组按元素进行计数。使用前提是需要先知道待排序数组的元素范围，将这些一定范围的元素置于新数组中，新数组的大小为待排序数组中最大元素与最小元素的差值。

维基上总结的四个步骤如下：

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

其中反向填充主要是为了避免重复元素落入新数组的同一索引处。

推荐文章：计数排序（Counting Sort）详解

在这里插入图片描述

图片来源：https://visualgo.net/en

文章来源:https://blog.csdn.net/JustDI0209/article/details/135676183
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章