排序算法之 '快速排序'

python實作快速排序，其主要的思想仍在遞歸的思想，如果能熟練掌握遞歸思想，這個排序過程也能熟練掌握

快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

排序流程

快速排序算法通過多次比較和交換來實作排序，其排序流程如下：

(1)首先設定一個分界值，通過該分界值将數組分成左右兩部分。

(2)将大于或等于分界值的資料集中到數組右邊，小于分界值的資料集中到數組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。

(3)然後，左邊和右邊的資料可以獨立排序。對于左側的數組資料，又可以取一個分界值，将該部分資料分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組資料也可以做類似處理。

(4)重複上述過程，可以看出，這是一個遞歸定義。通過遞歸将左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各資料排序完成後，整個數組的排序也就完成了。

算法穩定性

快速排序有兩個方向，左邊的i下标一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的數組下标，一般取為數組第0個元素。而右邊的j下标一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重複上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下标從1開始計)交換就會把元素3的穩定性打亂，是以快速排序是一個不穩定的排序算法，不穩定發生在中樞元素和a[j] 交換的時刻。

時間複雜度

• 最差時間分析是：

  O(n**2)

• 平均時間複雜度為：

  O(n*log2n)

  即n倍的log以2為底n的對數

Python實作

# 方法一：
def quick_sort(lst):
    if len(lst) < 2:
        return lst
    pivot = lst[0]
    less = [i for i in lst[1:] if i <= pivot]
    greater = [i for i in lst[1:] if i > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)


if __name__ == "__main__":
    print(quick_sort([2, 3, 1, 8, 5, 9, 4, 7]))

# [1, 2, 3, 4, 5, 7, 8, 9]

           

# 方法二：
# 這個算法實作太爛了，爛到不能再爛了！
def quick_sort(alist, start, end):
    low = start  # 序列左側指針（首次指向第一個元素）
    high = end  # 序列右側指針（首次指向最後一個元素）

    # 結束遞歸的條件
    if low > high:
        return

    mid = alist[low]  # 基數
    while low < high:
        # 向左偏移 high 指針
        while low < high:
            if alist[high] > mid:
                high -= 1
            else:
                alist[low] = alist[high]
                break

        # 向右偏移 low 指針
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break

    if low == high:
        alist[low] = mid

    # 将 quick_sort 遞歸作用到基數左側子序列
    quick_sort(alist, start, low - 1)
    # 将 quick_sort 遞歸作用到基數右側子序列
    quick_sort(alist, high + 1, end)

    return alist


if __name__ == '__main__':
    alist = [8, 4, 5, 7, 1, 3, 6, 2]
    print(quick_sort(alist, 0, len(alist) - 1))

    
# [1, 2, 3, 4, 5, 6, 7, 8]
           

抟扶搖而上者九萬裡