【Python 算法零基礎 4.排序 ② 冒泡排序】

目錄

一、引言

二、算法思想

三、時間復雜度和空間復雜度

1.時間復雜度

2.空間復雜度

四、冒泡排序的優缺點

1.算法的優點

2.算法的缺點

五、實戰練習

88. 合并兩個有序數組

算法與思路

① 合并數組

② 冒泡排序

2148. 元素計數

算法與思路

① 排序

② 初始化計數器

③?遍歷數組

④ 返回結果

1046. 最后一塊石頭的重量

算法與思路?

① 冒泡排序

② 石頭碰撞模擬

我走的很慢

從不是優秀的人

但是沒關系

我很少停下

脆弱會給我新力量

??????????????????? ?—— 25.5.19

選擇排序回顧：

① 初始化：從未排序序列開始，初始時整個數組都是未排序的。

② 尋找最小值：遍歷未排序部分的所有元素，找到其中的最小值。使用變量min_idx記錄最小值的索引，初始時假設當前未排序部分的第一個元素是最小的。

③ 交換元素：將找到的最小值與未排序部分的第一個元素交換位置。此時，未排序部分的第一個元素成為已排序序列的一部分。

④ 重復步驟 2-3：縮小未排序部分的范圍（從下一個元素開始），重復尋找最小值并交換的過程，直到整個數組排序完成。

def selection_sort(arr):for i in range(len(arr)):min_idx = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_idx]:arr[i], arr[min_idx] = arr[min_idx], arr[i]return arr

一、引言

? ? ? ? 冒泡排序（Bubble Sort）是一種簡單的排序算法，通過多次比較和交換相鄰的元素，將列表（數組）中的元素按照升序或降序排列

二、算法思想

? ? ? ? 冒泡排序的基本思想：每次遍歷數組，比較相鄰的兩個元素，如果它們的順序錯誤，就將它們交換，直到數組中的所有元素都被遍歷過

? ? ? ? 具體的算法步驟如下：

? ? ? ? ? ? ? ? ① 遍歷數組的第一個元素到最后一個元素。

? ? ? ? ? ? ? ? ② 對每一個元素，與其后一個元素進行比較。

? ? ? ? ? ? ? ? ③ 如果順序錯誤，就將它們交換。

? ? ? ? ? ? ? ? ④ 重復上述步驟，直到數組中的所有元素都被遍歷過至少一次。

三、時間復雜度和空間復雜度

1.時間復雜度

????????我們假設【比較】和【交換】的時間復雜度為O(1)

????????【冒泡排序】中有兩個嵌套循環

????????????????外循環正好運行n - 1次迭代。但內部循環運行變得越來越短:

????????????????當i = 0，內層循環n - 1次【比較】操作。

????????????????當i = 1，內層循環n - 2次【比較】操作。

????????????????當i = 2，內層循環n - 3次【比較】操作。

????????????????當i = n - 2，內層循環1次【比較】操作。

????????????????當i = n - 1，內層循環0次【比較】操作。

因此，總「比較」次數如下：(n - 1) + (n - 2) + ... + 1 + 0 = n (n - 1) / 2，總的時間復雜度為：O(n ^ 2)

2.空間復雜度

????????由于算法在執行過程中，只有【交換】變量時候采用了臨時變量的方式，而其它沒有采用任何的額外空間，所以空間復雜度為O(1)。

四、冒泡排序的優缺點

1.算法的優點

① 簡單易懂：冒泡排序的算法思想非常簡單，容易理解和實現。

② 穩定排序：冒泡排序是一種穩定的排序算法，即在排序過程中不會改變相同元素的相對順序。

2.算法的缺點

①?效率較低：由于需要進行多次比較和交換，冒泡排序在處理大規模數據時效率較低。

② 排序速度慢：對于大型數組，冒泡排序的時間復雜度較高，導致排序速度較慢。

五、實戰練習

88. 合并兩個有序數組

給你兩個按?非遞減順序?排列的整數數組?nums1?和?nums2，另有兩個整數?m?和?n?，分別表示?nums1?和?nums2?中的元素數目。

請你?合并?nums2?到?nums1?中，使合并后的數組同樣按?非遞減順序?排列。

注意：最終，合并后數組不應由函數返回，而是存儲在數組?nums1?中。為了應對這種情況，nums1?的初始長度為?m + n，其中前?m?個元素表示應合并的元素，后?n?個元素為?0?，應忽略。nums2?的長度為?n?。

示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結果是 [1,2,2,3,5,6] ，其中斜體加粗標注的為 nums1 中的元素。
示例 2：
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結果是 [1] 。
示例 3：
輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數組是 [] 和 [1] 。
合并結果是 [1] 。
注意，因為 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結果可以順利存放到 nums1 中。
提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

算法與思路

① 合并數組

將?nums2?的前?n?個元素依次復制到?nums1?的后?n?個位置（從索引?m?開始）。

② 冒泡排序

使用兩層循環對合并后的?nums1?進行升序排序：

????????外層循環遍歷每個元素（索引?i?從?0?到?mn-1）。

????????內層循環比較?i?之后的所有元素（索引?j?從?i+1?到?mn-1）。

若發現?nums1[i] > nums1[j]，則交換兩者位置。

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""for i in range(n):nums1[m + i] = nums2[i]mn = len(nums1)for i in range(mn):for j in range(mn - i -1):if nums1[j] > nums1[j + 1]:nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j]

2148. 元素計數

給你一個整數數組?nums?，統計并返回在?nums?中同時至少具有一個嚴格較小元素和一個嚴格較大元素的元素數目。

示例 1：

輸入：nums = [11,7,2,15]
輸出：2
解釋：元素 7 ：嚴格較小元素是元素 2 ，嚴格較大元素是元素 11 。
元素 11 ：嚴格較小元素是元素 7 ，嚴格較大元素是元素 15 。
總計有 2 個元素都滿足在 nums 中同時存在一個嚴格較小元素和一個嚴格較大元素。

示例 2：

輸入：nums = [-3,3,3,90]
輸出：2
解釋：元素 3 ：嚴格較小元素是元素 -3 ，嚴格較大元素是元素 90 。
由于有兩個元素的值為 3 ，總計有 2 個元素都滿足在 nums 中同時存在一個嚴格較小元素和一個嚴格較大元素。

提示：

1 <= nums.length <= 100
-105 <= nums[i] <= 105

算法與思路

① 排序

調用?bubbleSort?對數組進行升序排序。

② 初始化計數器

count = 0。

③?遍歷數組

對于每個元素?x，檢查其是否不等于數組的第一個元素（最小值）和最后一個元素（最大值）。若是，則?count += 1。

④ 返回結果

最終計數器的值。

class Solution:def bubbleSort(self, nums:List[int]):n = len(nums)for i in range(n):for j in range(n - i - 1):if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]def countElements(self, nums: List[int]) -> int:self.bubbleSort(nums)count = 0for x in nums:if x != nums[0] and x != nums[-1]:count += 1return count

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 <= 30
1 <= stones[i] <= 1000

算法與思路?

① 冒泡排序

每輪固定一個位置：通過外層循環?i?控制當前處理的位置，從?0?到?n-1。

比較后續所有元素：內層循環?j?從?i+1?開始，將?nums[i]?與后續所有元素比較。

交換較大值：若?nums[i] > nums[j]，則交換兩者，確保?i?位置的元素是當前未排序部分的最小值。

② 石頭碰撞模擬

初始化：獲取石頭數組長度?n，作為循環終止條件。

循環條件：當?n > 1?時，持續處理（確保至少有兩塊石頭可碰撞）。

排序：每次循環調用?bubbleSort?對數組升序排序，使最重的石頭位于末尾。

碰撞操作：取出最重的兩塊石頭?stones[-1]?和?stones[-2]，計算差值?v。

更新數組：

????????移除碰撞的石頭：通過兩次?pop()?移除末尾兩個元素，n?減 2。

????????添加新石頭：若?v != 0（兩塊石頭重量不同）或?n == 0（碰撞后無剩余石頭），將?v?加入數組，n?加 1。

返回結果：循環結束后，若?n == 1，返回剩余石頭?stones[0]

class Solution:def bubble_sort(arr):"""冒泡排序的標準實現"""n = len(arr)# 遍歷所有數組元素for i in range(n):# 最后i個元素已經就位，無需再比較for j in range(0, n-i-1):# 遍歷數組從0到n-i-1# 交換元素如果當前元素大于下一個元素if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrdef lastStoneWeight(self, stones: List[int]) -> int:n = len(stones)while n > 1:self.bubbleSort(stones)v = stones[-1] - stones[-2]n -= 2stones.pop()stones.pop()if v != 0 or n == 0:stones.append(v)n += 1return stones[0]