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

小億
84
2023-11-28 21:04:56
欄目: 編程語言

快速排序是一種基于分治的排序算法，其基本思想是選擇一個(gè)元素作為基準(zhǔn)，將小于基準(zhǔn)的元素放到基準(zhǔn)的左邊，大于基準(zhǔn)的元素放到基準(zhǔn)的右邊，然后對(duì)左右兩個(gè)子數(shù)組分別進(jìn)行快速排序。以下是用Python實(shí)現(xiàn)快速排序的代碼：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

使用示例：

arr = [3, 1, 5, 2, 4]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 輸出 [1, 2, 3, 4, 5]

在該實(shí)現(xiàn)中，我們選擇數(shù)組的第一個(gè)元素作為基準(zhǔn)，并使用列表推導(dǎo)式將小于基準(zhǔn)的元素放到less列表中，大于基準(zhǔn)的元素放到greater列表中。然后，我們遞歸地對(duì)less和greater進(jìn)行快速排序，并將結(jié)果合并后返回。

需要注意的是，這個(gè)實(shí)現(xiàn)中每次選擇第一個(gè)元素作為基準(zhǔn)，可能會(huì)導(dǎo)致在某些特定情況下（比如數(shù)組已經(jīng)是有序的）快速排序的效率下降。為了解決這個(gè)問題，可以選擇隨機(jī)的基準(zhǔn)元素，或者進(jìn)行優(yōu)化，比如三數(shù)取中法、取隨機(jī)數(shù)等。

0 踩