python快速排序算法怎么實(shí)現(xiàn)

小億
111
2023-08-15 18:20:44
欄目: 編程語言

快速排序是一種常用的排序算法，其算法思想是通過遞歸地將數(shù)組分為較小和較大的兩個(gè)子數(shù)組，然后不斷重復(fù)這個(gè)過程，直到整個(gè)數(shù)組有序。

下面是用Python實(shí)現(xiàn)的快速排序算法：

def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]  # 選擇中間元素作為基準(zhǔn)點(diǎn)
left = [x for x in arr if x < pivot]  # 小于基準(zhǔn)點(diǎn)的元素
middle = [x for x in arr if x == pivot]  # 等于基準(zhǔn)點(diǎn)的元素
right = [x for x in arr if x > pivot]  # 大于基準(zhǔn)點(diǎn)的元素
return quick_sort(left) + middle + quick_sort(right)  # 遞歸地對(duì)左右子數(shù)組進(jìn)行排序
# 示例
arr = [5, 3, 8, 2, 7, 1, 6, 4]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 輸出：[1, 2, 3, 4, 5, 6, 7, 8]

在這個(gè)實(shí)現(xiàn)中，我們選擇中間元素作為基準(zhǔn)點(diǎn)，然后分別將小于、等于和大于基準(zhǔn)點(diǎn)的元素放入對(duì)應(yīng)的子數(shù)組中。然后，我們遞歸地對(duì)左右子數(shù)組進(jìn)行排序，并將排好序的左子數(shù)組、中間元素和右子數(shù)組連接起來，最終得到整個(gè)數(shù)組的有序序列。

0 踩