Python3實現快速排序、歸并排序、堆排序

# -*- coding: utf-8 -*-
# @Time         : 2019-03-26 16:46
# @Author       : Jayce Wong
# @ProjectName  : leetcode
# @FileName     : sorting.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

import random

def quick_sort(data):
    """
    對于每一輪排序，先隨機選取范圍內的一個下標，該下標對應的值稱為主元，然后將小于主元的值挪到主元
    的左邊，大于主元的值挪到主元的右邊，即確保主元在正確的位置。然后下一輪只需要對主元左邊的數組和
    右邊的數組分別排序即可，數組大小減為原來的一半。
    每輪排序確定一個主元，該輪排序完成后待排序的兩個數組的長度變為原來的一半，可以看做是一個樹，
    根節點是原數組，每一輪會分裂一次，每個節點被分裂成2個子節點，直到該節點長度為1，不需再進行排序
    為止，這樣就一共需要logN輪，每輪每部需要比較N次，即時間復雜度nlogn
    快排是不穩定排序(相同大小的元素排序后不一定按照原順序)
    :param data: 待排序的數組
    """
    def sort(start, end):
        pivot = partition(start, end)
        if pivot > start:
            sort(start, pivot - 1)
        if pivot < end:
            sort(pivot + 1, end)

    def partition(start, end):
        idx = random.randint(start, end)  # 隨機選擇一個idx
        # 先將idx下標所在的值(主元)和末端的值交換
        data[idx], data[end] = data[end], data[idx]
        position = start  # position是下一個小于主元的值應在的位置
        for i in range(start, end):
            # 如果一個值小于主元，則檢查它是否在正確的位置，不正確的話則進行調整，使得它落到應在
            # 的位置
            if data[i] < data[end]:
                if i != position:
                    data[position], data[i] = data[i], data[position]
                position += 1
        # 還原主元應在的位置
        data[position], data[end] = data[end], data[position]
        return position

    if not data:
        return
    sort(0, len(data) - 1)

def merge_sort(data):
    """
    先將數組不斷進行對半分裂直到不可再分(最長子數組長度為1)，然后進行歸并，歸并的時候每次從兩個
    數組中選擇最小的元素。
    歸并排序是穩定算法，時間復雜度為nlogn
    :param data: 待排序的數組
    """
    def sort(start, end):
        if start < end:
            mid = (start + end) >> 1
            sort(start, mid)
            sort(mid + 1, end)
            merge(start, mid, end)

    def merge(start, mid, end):
        p1, p2 = start, mid + 1
        while p1 <= mid and p2 <= end:
            if data[p1] < data[p2]:
                temp.append(data[p1])
                p1 += 1
            else:
                temp.append(data[p2])
                p2 += 1
        if p1 <= mid:
            temp.extend(data[p1: mid + 1])
        if p2 <= end:
            temp.extend(data[p2: end + 1])

        # 【需要將輔助數組中的數還原到data中】
        while temp:
            data[start] = temp.pop(0)
            start += 1

    if not data:
        return
    temp = []  # 建立全局輔助數組，避免遞歸過程不斷創建
    sort(0, len(data) - 1)

def heap_sort(data):
    """
    堆排序是不穩定的一種排序算法，其時間復雜度是O(nlogn)

    當需要升序排序的時候，構建最大堆，反之構建最小堆。

    最大堆的定義是對于每一個非葉子節點，它的值大于等于它的子節點。最小堆的定義類似。

    以升序排序為例，堆排首先是從最后一個非葉子節點開始往左往上構建最大堆，目的是減少重復性工作，
    因為如果自頂向下構建最大堆的話難度大，而自底向上構建最大堆的話在對第x層的某個節點構建最大堆的
    時候可以確保第x+1層及以下的樹已滿足最大堆的定義
    :param data: 待排序的元素
    """
    def adjustHeap(cur_idx, length):
        """

        :param cur_idx: 待調整的子樹的根節點位置
        :param length: 樹中剩余的元素個數。隨著排序的進行，堆頂元素(根節點)會逐個被刪除，
                       導致樹中元素不斷減少
        """
        temp = data[cur_idx]  # 先記錄當前位置的元素
        # 由于最大堆的定義是父節點元素大于等于其子節點元素，因此將當前位置的元素和它的子節點元素
        # 進行大小比較,
        k = 2 * cur_idx + 1  # 左子節點的位置
        while k < length:  # 只在樹內遍歷
            # 如果右子節點的元素更大，則將k定位到右子節點，
            # 因為父節點的值需要不小于最大子節點的值
            if k + 1 < length and data[k] < data[k + 1]:
                k += 1

            # 如果子節點的元素大于根節點，則將子節點的值賦給父節點
            # 如果這里不使用賦值而是交換的話，會有多余的操作(如果這次調整需要不止一次交換的話)
            if data[k] > temp:
                data[cur_idx] = data[k]
                # 這時cur_idx保存的是temp可能要去到的位置，但是由于還有剩余的孫子節點沒有比較
                # 所以這里先不用交換，而是記錄下temp可能要去到的位置，最后再將其放到正確的位置
                cur_idx = k
            # 如果上層的子節點已經小于父節點，那么孫子節點一定不會大于父節點，因為我們已經構建了
            # 一個最大堆(在初始化構建最大堆時，我們是從最后一個非子節點開始自底向上構建的，所以
            # 在處理上層節點的時候其下層節點已經是符合最大堆定義的了，因此也符合這里的break條件)
            else:
                break
            # 檢查剩余的子節點
            k = 2 * k + 1

        data[cur_idx] = temp  # 將temp元素還原到正確的位置

    if not data:
        return

    """ 初始化構建最大堆 """
    # 從最后一個非葉子節點開始，往左遍歷，當第x層遍歷完之后從第x-1層的最右邊開始往左遍歷
    # 每次調整該節點使得滿足最大堆的要求
    for i in range((len(data) >> 1) - 1, -1, -1):
        adjustHeap(i, len(data))

    # 從構建好的最大堆取出堆頂元素(也就是最大值)，然后放到數組末尾(即將這個節點刪除)
    # 刪除之后需要重新調整堆的結構以滿足最大堆的定義。
    # 由于上一步已經構建了一個最大堆，因此這里只需要對新的根節點的元素進行調整即可
    for j in range(len(data) - 1, 0, -1):
        data[j], data[0] = data[0], data[j]
        adjustHeap(0, j)

def main():
    data = []
    for _ in range(10):
        data.append(random.randint(0, 9))

    print(data)
    quick_sort(data)
    merge_sort(data)
    heap_sort(data)
    print(data)

if __name__ == '__main__':
    main()