【Python 算法零基础 4.排序 ④ 计数排序】
从索引0到n-1n为数组长度）。假设当前索引i为最小值索引min_index。从i+1到n-1遍历，若找到更小元素，则更新min_index。若，则交换arr[i]与。设数组长度为n。遍历i从0到n-1（共n轮）。对于每轮i，遍历j从0到n-i-2。若，则交换两者。重复步骤 2-4，直到所有轮次完成。从索引1到n-1。将arr[i]存入current。从已排序部分的末尾（索引j = i-1）向前扫
目录
风永远吹向不缺风的山谷，祝你也是，缤纷争渡
—— 25.5.22
选择排序回顾
① 遍历数组：从索引 0 到 n-1（n 为数组长度）。
② 每轮确定最小值：假设当前索引 i 为最小值索引 min_index。从 i+1 到 n-1 遍历，若找到更小元素，则更新 min_index。
③ 交换元素：若 min_index ≠ i，则交换 arr[i] 与 arr[min_index]。
def selectionSort(arr):
n = len(arr)
for i in range(n):
min_index = i
# 找到最小值索引
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# 仅交换一次
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr冒泡排序回顾
① 初始化：设数组长度为 n。
② 外层循环：遍历 i 从 0 到 n-1（共 n 轮）。
③ 内层循环：对于每轮 i，遍历 j 从 0 到 n-i-1。
④ 比较与交换：若 arr[j] > arr[j+1]，则交换两者。
⑤ 结束条件：重复步骤 2-4，直到所有轮次完成。
def bubbleSort(arr: List[int]):
n = len(arr)
for i in range(n):
for j in range(n-i-1)：
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr插入排序回顾
① 遍历未排序元素：从索引 1 到 n-1。
② 保存当前元素：将 arr[i] 存入 current。
③ 元素后移：从已排序部分的末尾（索引 j = i-1）向前扫描，将比 current 大的元素后移。直到找到第一个不大于 current 的位置或扫描完所有元素。
④ 插入元素：将 current 放入 j+1 位置。
def insertSort(arr: List[int]):
n = len(arr)
for i in range(1, n):
current = arr[i]
j = i - 1
while j >= 0 and arr[j] > current:
# 将元素后移
arr[j+1] = arr[j]
j -= 1
# 放到第一个不大于要插入元素的元素后面
arr[j+1] = current
return arr一、引言
计数排序(Counting Sort)是一种基于哈希的排序算法。它的基本思想是通过统计每个元素的出现次数，然后根据统计结果将元素依次放入排序后的序列中。这种排序算法适用于元素范围较小的情况，例如整数范围在 0到 k之间。
二、算法思想
计数排序的核心是创建一个计数数组，用于记录每个元素出现的次数。然后，根据计数数组对原始数组进行排序。
具体步骤如下：
① 初始化一个长度为最大元素值加1的计数数组，所有元素初始化为 0。
② 遍历原始数组，将每个元素的值作为索引，在计数数组中对应位置加 1。
③ 将原数组清空。
④ 遍历计数器数组，按照数组中元素个数放回到原数组中。
三、算法分析
1.时间复杂度
Ⅰ、我们假设一次「 哈希」和「计数 」的时间复杂度均为O(1)。并且总共n个数，数字范围为（1，K）
Ⅱ、除了输入输出以外，「计数排序 」中总共有四个循环。
① 第一个循环，用于初始化「计数器数组」，时间复杂度O(k);
② 第二个循环，枚举所有数字，执行「哈希」和「计数」操作，时间复杂度O(n);
③ 第三个循环，枚举所有范围内的数字，时间复杂度O(k);
④ 第四个循环，是嵌套在第三个循环内的，最多走O(n)，虽然是嵌套，但是它和第三个循环是相加的关系，而并非相乘的关系。所以，总的时间复杂度为：O(n+k)
2.空间复杂度
假设最大的数字为k，则空间复杂度为：O(k)。
3.算法的优缺点
Ⅰ、算法的优点
① 简单易懂：计数排序的原理非常简单，容易理解和实现。
② 时间复杂度低：对于范围较小的元素，计数排序的时间复杂度非常优秀
③ 适用于特定场景：当元素的范围已知且较小时，计数排序可以高效地完成排序。
Ⅱ、算法的缺点
① 空间开销：计数排序需要额外的空间来存储计数数组，当元素范围较大时，可能会消耗较多的内存。
② 局限性：计数排序只适用于元素范围较小的情况，对于大规模数据或元素范围不确定的情况并不适用。
四、实战练习
75. 颜色分类
给定一个包含红色、白色和蓝色、共
n个元素的数组nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数
0、1和2分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
算法与思路
① 初始化计数数组
创建一个长度为 r+1 的数组 count，初始值全为 0。count 数组的索引范围为 0 到 r，用于统计每个元素的出现次数。
② 统计元素频率
遍历输入数组 arr，对于每个元素 x，将 count[x] 的值加 1。例如：若 arr = [2, 1, 3, 2]，则 count 数组最终为 [0, 1, 2, 1]（表示 0 出现 0 次，1 出现 1 次，2 出现 2 次，3 出现 1 次）。
③ 重构有序数组
初始化索引 index = 0，用于将元素放回原数组 arr。
遍历 count 数组，对于每个索引 v（从 0 到 r）：当 count[v] > 0 时，将 v 写入 arr[index]，并将 index 加 1。同时将 count[v] 减 1，直到 count[v] 变为 0。
class Solution:
def countingSort(self, arr, r):
# 定义一个计数列表，长度为 0 - r
count = [0 for i in range(r + 1)]
# 遍历传入列表中的每一个元素，在计数列表中进行计数
for x in arr:
count[x] += 1
index = 0
for v in range(r + 1):
while count[v] > 0:
arr[index] = v
index += 1
count[v] -= 1
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
self.countingSort(nums, 2)
1046. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为
x和y，且x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎；- 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回
0。示例：
输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
算法与思路
① 计数排序
初始化计数数组：创建长度为 r+1 的数组 count，初始值全为 0。
统计元素频率：遍历 arr，统计每个元素出现的次数，存入 count 数组。
重构有序数组：按索引从小到大遍历 count，将元素按频次放回 arr。
② 石头碰撞模拟
初始化：获取石头数组长度 n，作为循环终止条件。
循环条件：当 n > 1 时，持续处理（确保至少有两块石头可碰撞）。
排序：每次循环调用 countingSort 对数组升序排序，使最重的石头位于末尾。
碰撞操作：取出最重的两块石头 stones[-1] 和 stones[-2]，计算差值 v。
更新数组：
移除碰撞的石头：通过两次 pop() 移除末尾两个元素，n 减 2。
添加新石头：若 v != 0（两块石头重量不同），将 v 加入数组，n 加 1。若 v == 0（两块石头重量相同）且 n > 0，不添加新石头。
返回结果：循环结束后，当 n == 1，返回剩余石头 stones[0]
class Solution:
def countingSort(self, arr, r):
count = [0 for i in range(r + 1)]
for x in arr:
count[x] += 1
index = 0
for v in range(r + 1):
while count[v] > 0:
arr[index] = v
index += 1
count[v] -= 1
def lastStoneWeight(self, stones: List[int]) -> int:
n = len(stones)
while n > 1:
self.countingSort(stones, 1000)
v = stones[-1] - stones[-2]
n -= 2
stones.pop()
stones.pop()
if v != 0 or n == 0:
stones.append(v)
n += 1
return stones[0]
1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组
nums，其中nums[i]表示第i名学生的分数。另给你一个整数k。从数组中选出任意
k名学生的分数，使这k个分数间 最高分 和 最低分 的 差值 达到 最小化 。返回可能的 最小差值 。
示例 1：
输入：nums = [90], k = 1 输出：0 解释：选出 1 名学生的分数，仅有 1 种方法： - [90] 最高分和最低分之间的差值是 90 - 90 = 0 可能的最小差值是 0示例 2：
输入：nums = [9,4,1,7], k = 2 输出：2 解释：选出 2 名学生的分数，有 6 种方法： - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2 - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6 可能的最小差值是 2提示：
1 <= k <= nums.length <= 10000 <= nums[i] <= 10^5
算法与思路
① 计数排序
初始化计数数组：创建长度为 r+1 的数组 count，初始值全为 0。
统计元素频率：遍历 arr，统计每个元素出现的次数，存入 count 数组。
重构有序数组：按索引从小到大遍历 count，将元素按频次放回 arr。
② 最小差值
排序数组：调用 countingSort 对数组 nums 排序（假设元素范围为 0 到 100000）。
初始化结果：设置初始结果 res 为 100000（题目中元素的最大可能值）。
滑动窗口遍历：遍历所有可能的长度为 k 的子数组。子数组的起始索引 i 范围为 0 到 n - k（n 为数组长度）。对于每个子数组，计算其最大值（nums[i + k - 1]）和最小值（nums[i]）的差值。
更新最小差值：在所有差值中取最小值，更新 res。
返回结果：最终 res 即为所求的最小差值。
class Solution:
def countingSort(self, arr, r):
count = [0 for i in range(r + 1)]
for x in arr:
count[x] += 1
index = 0
for v in range(r + 1):
while count[v] > 0:
arr[index] = v
index += 1
count[v] -= 1
def minimumDifference(self, nums: List[int], k: int) -> int:
self.countingSort(nums, 100000)
# 题目中给的最大值是10 ^ 5
n = len(nums)
res = 100000
for i in range(n + 1 - k):
l = i
r = i + k -1
res = min(res, nums[r] - nums[l])
return res 
GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。
更多推荐
21
0- 0
已为社区贡献9条内容
所有评论(0)