目錄
一、引言
二、算法思想
三、算法分析
1.時間復雜度
2.空間復雜度
3.算法的優缺點
Ⅰ、算法的優點
Ⅱ、算法的缺點
四、實戰練習
75. 顏色分類
算法與思路
① 初始化計數數組
② 統計元素頻率
③ 重構有序數組
1046. 最后一塊石頭的重量
算法與思路
① 計數排序
② 石頭碰撞模擬
1984. 學生分數的最小差值
算法與思路
① 計數排序
②?最小差值
風永遠吹向不缺風的山谷，祝你也是，繽紛爭渡
???????????????????????????????????????????????????? ? ? ? ? ? ? ? ? ?—— 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 - 1while j >= 0 and arr[j] > current:# 將元素后移arr[j+1] = arr[j]j -= 1# 放到第一個不大于要插入元素的元素后面arr[j+1] = currentreturn 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 - rcount = [0 for i in range(r + 1)]# 遍歷傳入列表中的每一個元素，在計數列表中進行計數for x in arr:count[x] += 1index = 0for v in range(r + 1):while count[v] > 0:arr[index] = vindex += 1count[v] -= 1def 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] += 1index = 0for v in range(r + 1):while count[v] > 0:arr[index] = vindex += 1count[v] -= 1def lastStoneWeight(self, stones: List[int]) -> int:n = len(stones)while n > 1:self.countingSort(stones, 1000)v = stones[-1] - stones[-2]n -= 2stones.pop()stones.pop()if v != 0 or n == 0:stones.append(v)n += 1return 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] += 1index = 0for v in range(r + 1):while count[v] > 0:arr[index] = vindex += 1count[v] -= 1def minimumDifference(self, nums: List[int], k: int) -> int:self.countingSort(nums, 100000)# 題目中給的最大值是10 ^ 5n = len(nums)res = 100000for i in range(n + 1 - k):l = ir = i + k -1res = min(res, nums[r] - nums[l])return res 
通信（使用示例為SD2068）)
