一、快速排序

1、快速排序總結(jié)

• 快速排序是一種高效的排序算法，基于分治法的思想。

• 分區(qū)操作是快速排序的核心，將數(shù)組分為兩部分。

• 原地分區(qū)可以減少空間復(fù)雜度，提高效率。

• 快速排序的平均時間復(fù)雜度為 O(n log n)，但在最壞情況下（如輸入數(shù)組已經(jīng)排序）會退化到 O(n2)。

2、快速排序的基本思路

• 選擇基準(zhǔn)值（Pivot）：

  • 從數(shù)組中選擇一個元素作為基準(zhǔn)值?；鶞?zhǔn)值的選擇可以是數(shù)組的第一個元素、最后一個元素、中間元素，或者隨機(jī)選擇。

• 分區(qū)操作（Partition）：

  • 將數(shù)組分為兩部分：

    • 一部分包含小于基準(zhǔn)值的元素。

    • 另一部分包含大于基準(zhǔn)值的元素。

  • 基準(zhǔn)值最終會放在它最終的位置上。

• 遞歸排序：

  • 對小于基準(zhǔn)值的部分遞歸調(diào)用快速排序。

  • 對大于基準(zhǔn)值的部分遞歸調(diào)用快速排序。

• 合并結(jié)果：

  • 由于分區(qū)操作已經(jīng)將數(shù)組分為兩部分，遞歸排序后，數(shù)組自然有序，無需額外的合并操作。

3、快速排序和冒泡排序的區(qū)別

• 冒泡排序：

  • 優(yōu)點：實現(xiàn)簡單，代碼量少。

  • 缺點：效率低，時間復(fù)雜度為 O(n2)，不適用于大規(guī)模數(shù)據(jù)。

• 快速排序：

  • 優(yōu)點：效率高，平均時間復(fù)雜度為 O(n log n)，適合大規(guī)模數(shù)據(jù)。

  • 缺點：實現(xiàn)相對復(fù)雜，不穩(wěn)定排序算法。

二、代碼

def quick_sort(arr):# 如果數(shù)組長度小于等于1，直接返回if len(arr) <= 1:return arr# 選擇基準(zhǔn)值（這里選擇最后一個元素）pivot = arr[-1]# 分區(qū)操作left = [x for x in arr[:-1] if x <= pivot]  # 小于等于基準(zhǔn)值的元素right = [x for x in arr[:-1] if x > pivot]  # 大于基準(zhǔn)值的元素# 遞歸排序左右兩部分，并拼接結(jié)果return quick_sort(left) + [pivot] + quick_sort(right)# 示例
nums = [3, 2, 1, 5, 6, 4]
sorted_nums = quick_sort(nums)
print(sorted_nums)  # 輸出：[1, 2, 3, 4, 5, 6]