快速排序原理和步驟

快速排序是一種高效的排序算法，基于分治法（Divide and Conquer）來實現。其基本思想是通過一次排序將數組分成兩部分，其中一部分的所有元素都小于另一部分，然后遞歸地對這兩部分進行排序。以下是快速排序的詳細步驟：

1. 選擇基準元素

首先，從數組中選擇一個基準元素（pivot）。基準元素的選擇方法有多種，例如選擇第一個元素、最后一個元素、中間元素或隨機選擇一個元素。基準元素用于將數組分成兩部分。

2. 分區

通過遍歷數組，將所有小于基準元素的元素放到基準元素的左邊，所有大于基準元素的元素放到基準元素的右邊。這個過程稱為分區（partitioning）。分區后，基準元素的位置是其在最終排序數組中的正確位置。

3. 遞歸排序

對基準元素左邊的子數組和右邊的子數組分別遞歸地應用快速排序。這個過程將不斷分割和排序子數組，直到所有子數組的長度為1，表示數組已經有序。

4. 合并

由于快速排序是原地排序（in-place sorting），不需要額外的合并步驟。遞歸過程結束后，整個數組已經有序。

快速排序的完整步驟

1. 選擇基準： 選擇一個基準元素。
2. 分區： 將數組分成兩部分，一部分小于基準元素，另一部分大于基準元素。
3. 遞歸排序： 遞歸地對基準元素左邊和右邊的子數組進行排序。
4. 完成： 遞歸結束后，數組有序。

快速排序的偽代碼

void quickSort(vector<int>& arr, int low, int high) {if (low < high) {// 獲取分區點int pi = partition(arr, low, high);// 對分區點左邊的子數組進行遞歸排序quickSort(arr, low, pi - 1);// 對分區點右邊的子數組進行遞歸排序quickSort(arr, pi + 1, high);}
}int partition(vector<int>& arr, int low, int high) {// 選擇最后一個元素作為基準int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {// 如果當前元素小于或等于基準if (arr[j] <= pivot) {i++;// 交換 arr[i] 和 arr[j]swap(arr[i], arr[j]);}}// 交換 arr[i + 1] 和 arr[high] (或基準)swap(arr[i + 1], arr[high]);return (i + 1);
}

Python實現：

def quick_sort(arr):"""對數組進行快速排序:param arr: 待排序的數組:return: 已排序的數組"""# 如果數組的長度為0或1，直接返回數組if len(arr) <= 1:return arr# 選擇數組的最后一個元素作為基準pivot = arr[-1]# 定義兩個空列表，分別存放小于和大于基準的元素left = []right = []# 遍歷數組（不包括最后一個元素，即基準）for element in arr[:-1]:if element < pivot:left.append(element)else:right.append(element)# 遞歸地對左右兩個子數組進行快速排序，并合并return quick_sort(left) + [pivot] + quick_sort(right)