題目鏈接：力扣

選擇排序知識

1. 設第一個元素為比較元素，依次和后面的元素比較，比較完所有元素并找到最小元素，記錄最小元素下標，和第0個下表元素進行交換。
2. 在未排序區域中，重復上述操作，以此類推找出剩余最小元素將它換到前面，即完成排序。

解析

現在讓我們思考一下，冒泡排序和選擇排序有什么異同？

相同點：都是兩層循環，時間復雜度都為?O(n?2?); 都只使用有限個變量，空間復雜度?O(1)。
不同點：冒泡排序在比較過程中就不斷交換；而選擇排序增加了一個變量保存最小值 / 最大值的下標，遍歷完成后才交換，減少了交換次數。
事實上，冒泡排序和選擇排序還有一個非常重要的不同點，那就是：冒泡排序法是穩定的，選擇排序法是不穩定的。

排序算法的穩定性
假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

理解了穩定性的定義后，我們就能分析出：冒泡排序中，只有左邊的數字大于右邊的數字時才會發生交換，相等的數字之間不會發生交換，所以它是穩定的。

選擇排序算法如何實現穩定排序呢？

實現的方式有很多種，這里給出一種最簡單的思路：新開一個數組，將每輪找出的最小值依次添加到新數組中，選擇排序算法就變成穩定的了。

二元選擇排序

選擇排序算法也是可以優化的，既然每輪遍歷時找出了最小值，何不把最大值也順便找出來呢？這就是二元選擇排序的思想。

我們使用 minIndex 記錄最小值的下標，maxIndex 記錄最大值的下標。每次遍歷后，將最小值交換到首位，最大值交換到末尾，就完成了排序。

由于每一輪遍歷可以排好兩個數字，所以最外層的遍歷只需遍歷一半即可。

二元選擇排序中有一句很重要的代碼，它位于交換最小值和交換最大值的代碼中間：

def selectionSort(arr):for i in range(len(arr) - 1):minIndex = i  # 記錄最小元素的索引# 找出最小元素for j in range(i + 1, len(arr)):  if arr[j] < arr[minIndex]:minIndex = j# i不是最小元素時，將i和最小元素進行交換if i != minIndex:arr[i], arr[minIndex] = arr[minIndex], arr[i]return arr
if __name__=="__main__":nums = [1, 42, 65, 876, 34, 656, 4, 6757, 89, 24, 65, 42]print("start:", nums)

?方法1: bf排序

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:random.shuffle(nums)#將數組從大到小排序nums.sort(reverse=True)return nums[k-1]

執行用時：208 ms

時間復雜：O(nlogn)

方法2: 快速選擇 quick select

快排的改進，快排是一種分治思想的實現，沒做一層快排可以將數組分成兩份并確定一個數的位置。分析題目可以知道，要找到第 k 個最大的元素，找到這個元素被劃分在哪邊就可以了。

快速排序（英語：Quicksort），又稱分區交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾（Tony Hoare ）提出。在平均狀況下，排序?n 個項目要??O(nlogn) 次比較。在最壞狀況下則需要?O(n?2?) 次比較，但這種狀況并不常見。事實上，快速排序Θ(nlogn) 通常明顯比其他演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的 2 個子序列，然后遞歸地排序兩個子序列。

以「升序排列」為例，其基本步驟為 [摘自@維基百科]：

1. 挑選基準值：從數列中挑出一個元素，稱為“基準”（pivot）；
2.? 分割（partition）：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數可以到任何一邊）。在這個分割結束之后，對基準值的排序就已經完成；
3. 遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。

遞歸到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序.

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def partition(arr: List[int], low: int, high: int) -> int:pivot = arr[low]                                        # 選取最左邊為pivotleft, right = low, high     # 雙指針while left < right:while left<right and arr[right] >= pivot:          # 找到右邊第一個<pivot的元素right -= 1arr[left] = arr[right]                             # 并將其移動到left處while left<right and arr[left] <= pivot:           # 找到左邊第一個>pivot的元素left += 1arr[right] = arr[left]                             # 并將其移動到right處arr[left] = pivot           # pivot放置到中間left=right處return leftdef randomPartition(arr: List[int], low: int, high: int) -> int:pivot_idx = random.randint(low, high)                   # 隨機選擇pivotarr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]     # pivot放置到最左邊return partition(arr, low, high)                        # 調用partition函數def topKSplit(arr: List[int], low: int, high: int, k: int) -> int:# mid = partition(arr, low, high)                   # 以mid為分割點【非隨機選擇pivot】mid = randomPartition(arr, low, high)               # 以mid為分割點【隨機選擇pivot】if mid == k-1:                                      # 第k小元素的下標為k-1return arr[mid]                                 #【找到即返回】elif mid < k-1:return topKSplit(arr, mid+1, high, k)           # 遞歸對mid右側元素進行排序else:return topKSplit(arr, low, mid-1, k)            # 遞歸對mid左側元素進行排序n = len(nums)return topKSplit(nums, 0, n-1, n-k+1)                   # 第k大元素即為第n-k+1小元素

這個代碼實現了快速選擇算法的一個變種，用來找出數組中第 k 大的元素。這個實現采用了“快速排序”的分區思想，并通過隨機選擇軸點（pivot）來提高算法的效率和避免最壞情況的發生。以下是代碼的逐步解析：

partition 函數

• 這個函數接受一個數組 arr 和兩個指針 low 和 high 作為參數，用來確定數組的操作區間。
• 它首先選擇 low 索引處的元素作為軸點（pivot）。
• 使用兩個指針 left 和 right 從數組的兩端開始，向中間移動，并根據元素與軸點的比較結果進行交換，直到兩個指針相遇。
• 最終，軸點元素被放置在其最終位置上，該位置左邊的所有元素都不大于軸點，右邊的所有元素都不小于軸點。
• 函數返回軸點的最終位置

這個代碼實現了快速選擇算法的一個變種，用來找出數組中第 k 大的元素。這個實現采用了“快速排序”的分區思想，并通過隨機選擇軸點（pivot）來提高算法的效率和避免最壞情況的發生。以下是代碼的逐步解析：

randomPartition 函數

• 為了避免在特定的數組順序下陷入最壞情況（如已排序的數組），該函數首先在 low 和 high 范圍內隨機選擇一個軸點索引 pivot_idx。
• 然后，它將選定的軸點與區間的第一個元素交換，確保隨機選擇的軸點被移到了區間的開頭。
• 最后，調用 partition 函數執行實際的分區操作。

topKSplit 函數

• 這個函數是快速選擇算法的核心，它遞歸地在數組的一個子區間內查找第 k 小（或第 k 大）的元素。
• 它首先調用 randomPartition 對當前考慮的數組區間進行分區，然后根據分區后軸點的位置與 k 的關系決定下一步的操作。
• 如果軸點恰好是第 k-1 個元素（因為數組索引從0開始），那么就找到了第 k 小的元素，直接返回。
• 如果軸點的位置小于 k-1，說明第 k 小的元素位于軸點右側的區間內，因此對右側區間遞歸調用 topKSplit。
• 如果軸點的位置大于 k-1，說明第 k 小的元素位于軸點左側的區間內，因此對左側區間遞歸調用 topKSplit。

主函數 findKthLargest

• 最后，findKthLargest 函數通過調用 topKSplit 并傳入整個數組、起始索引 0、結束索引 n-1 和 n-k+1（因為第 k 大元素是第 n-k+1 小元素）來找到第 k 大的元素。

3 partiton

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def quick_select(nums, k):pivot = random.choice(nums)big, equal, small = [], [], []# 將大于、小于、等于 pivot 的元素劃分至 big, small, equal 中for num in nums:if num > pivot:big.append(num)elif num < pivot:small.append(num)else:equal.append(num)if k <= len(big):# 第 k 大元素在 big 中，遞歸劃分return quick_select(big, k)if len(nums) - len(small) < k:# 第 k 大元素在 small 中，遞歸劃分return quick_select(small, k - len(nums) + len(small))# 第 k 大元素在 equal 中，直接返回 pivotreturn pivotreturn quick_select(nums, k)

1. 快速選擇函數 quick_select：

這是一個內部定義的輔助函數，用于實現快速選擇算法。它接受當前考慮的數組 nums 和目標 k 作為參數。

2. 選擇軸點：

pivot = random.choice(nums) 從 nums 中隨機選擇一個元素作為軸點（Pivot）。這種隨機化策略有助于提高算法的平均性能，避免在特定情況下的性能退化。

3. 分區：

算法遍歷數組 nums，根據元素與軸點的大小關系，將其分配到三個列表中：big（存儲所有大于軸點的元素）、equal（存儲所有等于軸點的元素）、small（存儲所有小于軸點的元素）。

4. 遞歸選擇：

• 如果 k 小于等于 big 列表的長度，說明第 k 大的元素在 big 中，因此遞歸地在 big 中尋找第 k 大的元素。
• n-1-k+1
• 如果 k 大于 nums 減去 small 列表長度的結果（即 k 在減去所有小于軸點的元素后仍大于 big 和 equal 的總長度），說明第 k 大的元素在 small 中。此時，需要在 small 中尋找新的第 k - (len(nums) - len(small)) 大的元素，因為我們已經排除了一部分更大的元素。
• 如果上述兩種情況都不滿足，說明第 k 大的元素在 equal 中，由于 equal 中的所有元素都等于軸點值 pivot，因此直接返回 pivot。

5.?返回結果：

• 最終，通過調用 quick_select(nums, k) 執行快速選擇邏輯，并返回找到的第 k 大的元素。

時間復雜度：快速選擇算法的平均時間復雜度為 O(n)，但在最壞情況下可能會達到 O(n2)。

通過隨機選擇軸點，快速選擇算法能夠在大多數情況下避免最壞情況的發生，從而保持較高的效率。

精講：. - 力扣（LeetCode）

. - 力扣（LeetCode）

空間復雜度 O(logN)?：?劃分函數的平均遞歸深度為O(logN)?

方法3: 堆