Python實現快速排序算法

一、什麼是快速排序算法

快速排序算法（Quick Sort），是一種高效的、比較常用的排序算法。快速排序主要思想是通過選擇一個”基準”數，將待排序序列分成兩個子序列，在這兩個子序列中分別對每個元素進行比較和排序，從而達到排序整個序列的目的。

二、快速排序算法的原理

快速排序的原理很簡單，其主要分為三步：

1. 選擇一個數作為基準數，一般為第一個數。

2. 分區過程：將原序列分為兩個子序列，小於基準數的放在左邊，大於等於基準數的放在右邊。分區的過程可以使用快慢指針或者左右指針來實現。

3. 遞歸實現：遞歸地對左右兩個子序列進行同樣的操作，直到所有子序列的長度都為 1。

三、代碼實現

def quick_sort(arr, left, right):
    if left >= right:
        return
    i = left
    j = right
    base = arr[i] # 選擇第一個數為基準數
    while i < j:
        while i = base:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] < base:
            i += 1
        arr[j] = arr[i]
    arr[i] = base
    quick_sort(arr, left, i - 1)
    quick_sort(arr, i + 1, right)

四、時間複雜度分析

在最優情況下，每次劃分所得的兩個子序列的長度大致相等，此時快排的時間複雜度為 O(nlogn)，其中n為數組的長度。

在最壞情況下，每次劃分所得的兩個子序列的長度分別為 1 和 (n-1)，此時快排的時間複雜度為 O(n^2)。因此，為了避免最壞情況的出現，需要採取一些優化措施。

五、快速排序的優化

1. 隨機選擇基準數，避免最壞情況的出現。

import random

def quick_sort(arr, left, right):
    if left >= right:
        return
    i = left
    j = right
    base = arr[random.randint(left, right)]
    while i < j:
        while i = base:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] < base:
            i += 1
        arr[j] = arr[i]
    arr[i] = base
    quick_sort(arr, left, i - 1)
    quick_sort(arr, i + 1, right)

2. 當序列長度小於某一個值時，採用插入排序。

def insert_sort(arr, left, right):
    for i in range(left+1, right+1):
        j = i
        while j > left and arr[j] = right:
        return
    if right - left <= 10:
        insert_sort(arr, left, right)
        return
    i = left
    j = right
    base = arr[random.randint(left, right)]
    while i < j:
        while i = base:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] < base:
            i += 1
        arr[j] = arr[i]
    arr[i] = base
    quick_sort(arr, left, i - 1)
    quick_sort(arr, i + 1, right)

六、總結

快速排序是一種非常高效的排序算法，其原理簡單，代碼實現也比較容易。但是，在最壞情況下，快排的時間複雜度會達到 O(n^2)，因此需要採取一些優化措施來避免最壞情況的出現。

通過對快速排序算法的優化，可以提高算法的效率。在實際應用中，快排算法經常被使用，如對數據進行排序、在數據處理場景中查找中位數等。