排序算法

快速排序

插入排序

歸并排序

希爾排序

堆排序

快速排序

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

步驟為：

• 挑選基準值：從數(shù)列中挑出一個元素，稱為"基準"（pivot）;
• 分割：重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數(shù)可以到任何一邊）。在這個分割結(jié)束之后，對基準值的排序就已經(jīng)完成;
• 遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。

遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時該數(shù)列顯然已經(jīng)有序。

選取基準值有數(shù)種具體方法，此選取方法對排序的時間性能有決定性影響。

def quick_sort2(lst):"""快速排序"""def partition(lst, left, right):#默認選擇列表最左元素作為樞軸pivot_value = lst[left]while left<right:while left<right and lst[right]>=pivot_value:right-=1#當右指針對應元素小于樞軸的值，將左右指針對應元素交換，使小于樞軸的值位于樞軸的左側(cè)lst[left], lst[right] = lst[right], lst[left]while left<right and lst[left]<=pivot_value:left+=1#當左指針對應元素大于樞軸的值，將左右指針對應元素交換，使大于樞軸的值位于樞軸的右側(cè)lst[left], lst[right] = lst[right], lst[left]return leftdef q_sort(lst, left, right):if left>=right:returnpivot_key = partition(lst, left, right)q_sort(lst, left, pivot_key-1)q_sort(lst, pivot_key+1, right)if not lst or len(lst)==0:return lstq_sort(lst, 0, len(lst)-1)return lst

歸并排序

def mergesort(seq):"""歸并排序"""if len(seq) <= 1:return seqmid = len(seq) / 2 # 將列表分成更小的兩個列表# 分別對左右兩個列表進行處理，分別返回兩個排序好的列表left = mergesort(seq[:mid])right = mergesort(seq[mid:])# 對排序好的兩個列表合并，產(chǎn)生一個新的排序好的列表return merge(left, right)def merge(left, right):"""合并兩個已排序好的列表，產(chǎn)生一個新的已排序好的列表"""result = [] # 新的已排序好的列表i = 0 # 下標j = 0# 對兩個列表中的元素 兩兩對比。# 將最小的元素，放到result中，并對當前列表下標加1while i < len(left) and j < len(right):if left[i] <= right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result += left[i:]result += right[j:]return result

kth-largest-element-in-an-array

• 思路 1: sort 后取第 k 個，最簡單直接，復雜度 O(N log N) 代碼略

• 思路 2: 使用最小堆，復雜度 O(N log k)

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# note that in practice there is a more efficient python build-in function heapq.nlargest(k, nums)min_heap = []for num in nums:if len(min_heap) < k:heapq.heappush(min_heap, num)else:if num > min_heap[0]:heapq.heappushpop(min_heap, num)return min_heap[0]

思路 3: Quick select，方式類似于快排，每次 partition 后檢查 pivot 是否為第 k 個元素，如果是則直接返回，如果比 k 大，則繼續(xù) partition 小于 pivot 的元素，如果比 k 小則繼續(xù) partition 大于 pivot 的元素。相較于快排，quick select 每次只需 partition 一側(cè)，因此平均復雜度為 O(N)。

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:k -= 1 # 0-based indexdef partition(left, right):pivot_idx = random.randint(left, right)pivot = nums[pivot_idx]nums[right], nums[pivot_idx] = nums[pivot_idx], nums[right]partition_idx = leftfor i in range(left, right):if nums[i] > pivot:nums[partition_idx], nums[i] = nums[i], nums[partition_idx]partition_idx += 1nums[right], nums[partition_idx] = nums[partition_idx], nums[right]return partition_idxleft, right = 0, len(nums) - 1while True:partition_idx = partition(left, right)if partition_idx == k:return nums[k]elif partition_idx < k:left = partition_idx + 1else:right = partition_idx - 1

總結(jié)

以上是生活随笔為你收集整理的LeetCode Hot100 ---- 排序专题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。