计数排序17 Mar 2025 | 6 分钟阅读 它是一种线性时间排序算法，通过不进行比较来更快地工作。它假设要排序的数字在 1 到 k 之间，其中 k 很小。 基本思想是确定最终排序数组中每个数字的“排名”。 计数排序使用三个数组
首先 C [x] 是 A [j] 中等于 x 的元素的数量
我们将 B[C [x]] =A[j] 如果存在重复项，我们在复制后将 C [i] 递减。 说明 步骤 1： 循环初始化数组 R 为 'o'。 但是，在第一步中，循环变量初始化为 1 到 k 还是 0 到 k 存在矛盾。 因为 0 和 1 基于数组 A（输入数组）中出现的最小值。 基本上，我们从输入数组 'A' 中的最小值开始 I。 步骤 3 到 4 的循环检查每个输入元素。 如果输入元素的值为 'i'，则递增 C [i]。 因此，在步骤 5 之后，C [i] 包含等于 I 的输入元素的数量，对于每个整数 i=0, 1, 2.....k 步骤 6 到 8 循环确定对于每个 i=0, 1.....有多少个输入元素小于或等于 i 步骤 9 到 11 的循环将每个元素 A [j] 放入输出数组 B 中的正确排序位置。 对于每个 A [j]，值 C [A[j]] 是 A [j] 在输出数组 B 中的正确最终位置，因为有 C [A[j]] 个元素小于或等于 A [i]。 由于元素可能不唯一，因此我们在将值 A [j] 放入数组 B 中时，每次递减 C[A[j]，递减 C[A[j] 会导致具有等于 A [j] 的值的下一个输入元素在输出数组中紧接在 A [j] 之前的位置。 运行时间分析
总时间是 θ(k+n) 时间。 注意
示例： 说明计数排序在数组中的操作。 解决方案  图：初始 A 和 C 数组  图：A [1] = 7 已处理  图：A [2] = 1 已处理  图：A [3] = 3 已处理  图：A [4] = 1 已处理  图：A [5] = 2 已处理 更新后的 C 是 图：C 现在包含 A 的元素计数 注意：这里，'A' 的项目逐个扫描，并将成为 'C' 中的一个位置，并且该项目被访问的次数将在 'C' 数组中的一个项目中被提及，如果任何项目再次被访问，则它会更新或计数器增加 1。现在，将执行循环 i= 2 到 7，并带有语句 通过应用这些条件，我们将得到 C 更新，正如我从 2 到 7 所述 C [2] = C [2] + C [1] C [3] = C [3] + C [2] C [2] = 2 + 2 C [3] = 2 + 4 C [2] = 4 C [3] = 6 C [4] = C [4] + C [3] C [5] = C [5] + C [4] C [4] = 2 + 6 C [5] = 1 +8 C [4] = 8 C [5] = 9 C [6] = C [6] + C [5] C [7] = C [7] + C [6] C [6] = 0 + 9 C [7] = 2 + 9 C [6] = 9 C [7] = 11 因此，更新后的 C 是 图：C 设置为对 A 的每个数字进行排名 现在，我们将找到新的数组 B  现在将应用两个条件
我们通过 '1' 逐个递减计数器 步骤 1B [C [A [11]]] = A [11] C [A [11] = C [A [11]-1 B [C [3] = 3 C [3] = C [3] -1 B [6] = 3 C [3] = 5  图：A [11] 放置在输出数组 B 中 步骤 2B [C [A [10]]] = A [10] C [A [10]] = C [A [10]]-1 B [C [4]] =4 C [4] = C [4] -1 B [8] = 4 C [4] = 7  图：A [10] 放置在输出数组 B 中 步骤 3B [C [A [9]] = A [9] C [A [9] = C [A [9]]-1 B [C [2]] = A [2] C [2] = C [2]-1 B [4] = 2 C [2] = 3  图：A [9] 放置在输出数组 B 中 步骤 4B [C [A [8]]] = A [8] C [A [8]] =C [A [8]] -1 B [C [7]] =7 C [A [8]] = C [7]-1 B [11] =7 C [7] = 10  图：A [8] 放置在输出数组 B 中 步骤 5B [C [A [7]]] = A [7] C [A [7]] = C [A [7]] - 1 B [C [5]] = 5 C [5] = C [5] - 1 B [9] = 5 C [5] =8  图：A [7] 放置在输出数组 B 中 步骤 6B [C [A [6]]] = A [6] C [A [6]] = C [A [6]] - 1 B [C [4]] = 4 C [4] = C [4] - 1 B [7] = 4 C [4] = 6  图：A [6] 放置在输出数组 B 中 步骤 7B [C [A [5]]] = A [5] C [A [5] = C [A [5]] -1 B [C [2] =2 C [2] = C [2] - 1 B [3] = 2 C [2] = 2  图：A [5] 放置在输出数组 B 中 步骤 8B [C [A [4]]] = A [4] C [A [4]] = C [A [4]] - 1 B [C [1] = 1 C [1] = C [1] - 1 B [2] = 1 C [1] = 1  图：A [4] 放置在输出数组 B 中 步骤 9B [C [A [3]]] = A [3] C [A [3]] = C [A [3]] - 1 B [C [3] = 3 C [3] = C [3] - 1 B [5] = 3 C [3] = 4  图：A [3] 放置在输出数组 B 中 步骤 10B [C [A [2]]] = A [2] C [A [2]] = C [A [2]] - 1 B [C [1]] = 1 C [1] = C [1] - 1 B [1] = 1 C [1] = 0  图：A [2] 放置在输出数组 B 中 步骤 11B [C [A [1]]] = A [1] C [A [1]] = C [A [1]] - 1 B [C [7]] = 7 C [7] = C [7] - 1 B [10] = 7 C [7] = 9  图：B 现在包含最终排序的数据。 下一个主题桶排序 |
我们请求您订阅我们的新闻通讯以获取最新更新。
我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Python
Java
JavaScript
SQL
C
C++
HTML
CSS
React
Node.js
Spring Boot
C#
PHP
MySQL
MongoDB
AI
ML
DSA
DBMS
OS
Aptitude
Reasoning