快速排序：用Python實現簡單高效的數組排序

快速排序是一種常用的排序演算法之一，也是一種高效的排序方法，尤其擅長對大規模數據集排序。

一、演算法原理

快速排序的基本思路是：選擇一個基準元素，將數組分為兩個子數組，小於基準的位於左子數組，大於基準的位於右子數組，然後遞歸地對左右子數組進行排序，最後合併兩個子數組。

具體的實現方法有很多，我們舉一個例子：

<pre>
def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #選取基準元素
        pivot = array[0]
        #將小於基準的元素放到左邊，大於基準的元素放到右邊
        left = [x for x in array[1:] if x < pivot]
        right = [x for x in array[1:] if x >= pivot]
        #遞歸排序左右子數組
        return quick_sort(left) + [pivot] + quick_sort(right)
</pre>

二、演算法優化

快速排序的平均時間複雜度為O(nlogn)，是一種非常高效的排序演算法。不過，在實際應用中，快排也有一些局限性：

1、如果已經排好序的數組會使遞歸樹的深度達到O(n)，時間複雜度變為O(n^2)。這種情況下，可以隨機選取基準元素來避免。

2、在業務上，如果數組中有大量重複的元素，快排的效率會大大降低。這種情況下，可以選擇三路快排演算法。

我們來看看如何優化快速排序演算法：

1、隨機選取基準元素

可以通過random模塊來隨機選取基準元素，代碼如下：

<pre>
import random

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #隨機選取基準元素
        index = random.randint(0, len(array) - 1)
        pivot = array[index]
        #將小於基準的元素放到左邊，大於基準的元素放到右邊
        left = [x for x in array[:index] + array[index+1:] if x < pivot]
        right = [x for x in array[:index] + array[index+1:] if x >= pivot]
        #遞歸排序左右子數組
        return quick_sort(left) + [pivot] + quick_sort(right)
</pre>

2、三路快排

三路快排演算法是對快速排序演算法的一種優化，主要應用於處理有大量重複元素的數組。它不但能減少遞歸深度，也能減少時間複雜度。

思路是將數組分為小於、等於、大於基準元素的三個區間，然後遞歸對小於和大於的部分繼續進行三路快排，以此類推。

<pre>
def quick_sort_3w(array):
    if len(array) <= 1:
        return array
    else:
        #選取基準元素
        pivot = array[0]
        lt = [x for x in array if x < pivot] #小於基準元素的數組
        eq = [x for x in array if x == pivot] #等於基準元素的數組
        gt = [x for x in array if x > pivot] #大於基準元素的數組
        #遞歸排序三個子數組
        return quick_sort_3w(lt) + eq + quick_sort_3w(gt)
</pre>

三、演算法實現

現在，我們可以來實現一個完整的快速排序演算法，在實現過程中可以選擇以上兩種優化演算法。

<pre>
import random

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #隨機選取基準元素
        index = random.randint(0, len(array) - 1)
        pivot = array[index]
        #將小於基準的元素放到左邊，大於基準的元素放到右邊
        left = [x for x in array[:index] + array[index+1:] if x < pivot]
        right = [x for x in array[:index] + array[index+1:] if x >= pivot]
        #遞歸排序左右子數組
        return quick_sort(left) + [pivot] + quick_sort(right)

def quick_sort_3w(array):
    if len(array) <= 1:
        return array
    else:
        #選取基準元素
        pivot = array[0]
        lt = [x for x in array if x < pivot] #小於基準元素的數組
        eq = [x for x in array if x == pivot] #等於基準元素的數組
        gt = [x for x in array if x > pivot] #大於基準元素的數組
        #遞歸排序三個子數組
        return quick_sort_3w(lt) + eq + quick_sort_3w(gt)
</pre>

四、總結

快速排序是一種常用的高效排序演算法，一般情況下優於冒泡排序、插入排序、選擇排序等演算法。

快速排序的基本思路是分治法，通過遞歸將數組分為兩個子數組進行排序，最後合併。

如果數組中有大量重複元素，可以採用三路快排演算法進行優化。