以下是用 Python 實現的 QuickSort 函式，用於將傳入的一維陣列利用快速排序法，由小至大排序陣列元素：
def quick_sort(arr):
# 定義快速排序的主函式
def _quick_sort(items, low, high):
if low < high:
# 獲取分割點
pivot_index = partition(items, low, high)
# 對左子陣列進行遞迴排序
_quick_sort(items, low, pivot_index)
# 對右子陣列進行遞迴排序
_quick_sort(items, pivot_index + 1, high)
# 定義分割函式
def partition(items, low, high):
pivot = items[low] # 選擇最左邊的元素為基準點
left = low + 1
right = high
done = False
while not done:
while left <= right and items[left] <= pivot:
left += 1
while items[right] >= pivot and right >= left:
right -= 1
if right < left:
done = True
else:
# 交換左右兩個不符合條件的元素
items[left], items[right] = items[right], items[left]
# 交換基準點元素與右指針所指元素
items[low], items[right] = items[right], items[low]
return right
# 調用主函式
_quick_sort(arr, 0, len(arr) - 1)
return arr
# 測試範例
sample_array = [34, 7, 23, 32, 5, 62]
sorted_array = quick_sort(sample_array)
print("排序後的陣列：", sorted_array)
-
quick_sort 函式：
- 主函式 quick_sort 接受一個一維陣列 arr，並調用內部的 _quick_sort 函式對陣列進行排序。
-
_quick_sort 函式：
- _quick_sort 是實現快速排序的主遞迴函式。它接受一個子陣列範圍（由 low 和 high 指定），並對該範圍內的元素進行排序。
- 如果 low < high，則調用 partition 函式進行分割，並獲取分割點 pivot_index。
- 然後對基準點左右兩邊的子陣列分別進行遞迴排序。
-
partition 函式：
- partition 函式負責選擇基準點（本例中選擇最左邊的元素），並將陣列分割為兩部分：一部分包含所有小於等於基準點的元素，另一部分包含所有大於基準點的元素。
- 它通過左右指針 left 和 right 遍歷陣列，並交換不符合條件的元素，直到所有元素都正確分割到基準點兩側。
- 最後，將基準點元素與右指針所指的元素交換，並返回基準點的位置 right。
測試
在範例測試中，我們使用一個樣本陣列 [34, 7, 23, 32, 5, 62] 進行排序。調用 quick_sort 函式後，輸出排序後的陣列為 [5, 7, 23, 32, 34, 62]。
阿摩線上測驗
登入