Python3實(shí)現(xiàn)快速排序、歸并排序、堆排序

# -*- 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):
    """
    對(duì)于每一輪排序，先隨機(jī)選取范圍內(nèi)的一個(gè)下標(biāo)，該下標(biāo)對(duì)應(yīng)的值稱為主元，然后將小于主元的值挪到主元
    的左邊，大于主元的值挪到主元的右邊，即確保主元在正確的位置。然后下一輪只需要對(duì)主元左邊的數(shù)組和
    右邊的數(shù)組分別排序即可，數(shù)組大小減為原來的一半。
    每輪排序確定一個(gè)主元，該輪排序完成后待排序的兩個(gè)數(shù)組的長(zhǎng)度變?yōu)樵瓉淼囊话?，可以看做是一個(gè)樹，
    根節(jié)點(diǎn)是原數(shù)組，每一輪會(huì)分裂一次，每個(gè)節(jié)點(diǎn)被分裂成2個(gè)子節(jié)點(diǎn)，直到該節(jié)點(diǎn)長(zhǎng)度為1，不需再進(jìn)行排序
    為止，這樣就一共需要logN輪，每輪每部需要比較N次，即時(shí)間復(fù)雜度nlogn
    快排是不穩(wěn)定排序(相同大小的元素排序后不一定按照原順序)
    :param data: 待排序的數(shù)組
    """
    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)  # 隨機(jī)選擇一個(gè)idx
        # 先將idx下標(biāo)所在的值(主元)和末端的值交換
        data[idx], data[end] = data[end], data[idx]
        position = start  # position是下一個(gè)小于主元的值應(yīng)在的位置
        for i in range(start, end):
            # 如果一個(gè)值小于主元，則檢查它是否在正確的位置，不正確的話則進(jìn)行調(diào)整，使得它落到應(yīng)在
            # 的位置
            if data[i] < data[end]:
                if i != position:
                    data[position], data[i] = data[i], data[position]
                position += 1
        # 還原主元應(yīng)在的位置
        data[position], data[end] = data[end], data[position]
        return position

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

def merge_sort(data):
    """
    先將數(shù)組不斷進(jìn)行對(duì)半分裂直到不可再分(最長(zhǎng)子數(shù)組長(zhǎng)度為1)，然后進(jìn)行歸并，歸并的時(shí)候每次從兩個(gè)
    數(shù)組中選擇最小的元素。
    歸并排序是穩(wěn)定算法，時(shí)間復(fù)雜度為nlogn
    :param data: 待排序的數(shù)組
    """
    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])

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

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

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

    當(dāng)需要升序排序的時(shí)候，構(gòu)建最大堆，反之構(gòu)建最小堆。

    最大堆的定義是對(duì)于每一個(gè)非葉子節(jié)點(diǎn)，它的值大于等于它的子節(jié)點(diǎn)。最小堆的定義類似。

    以升序排序?yàn)槔?，堆排首先是從最后一個(gè)非葉子節(jié)點(diǎn)開始往左往上構(gòu)建最大堆，目的是減少重復(fù)性工作，
    因?yàn)槿绻皂斚蛳聵?gòu)建最大堆的話難度大，而自底向上構(gòu)建最大堆的話在對(duì)第x層的某個(gè)節(jié)點(diǎn)構(gòu)建最大堆的
    時(shí)候可以確保第x+1層及以下的樹已滿足最大堆的定義
    :param data: 待排序的元素
    """
    def adjustHeap(cur_idx, length):
        """

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

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

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

    if not data:
        return

    """ 初始化構(gòu)建最大堆 """
    # 從最后一個(gè)非葉子節(jié)點(diǎn)開始，往左遍歷，當(dāng)?shù)趚層遍歷完之后從第x-1層的最右邊開始往左遍歷
    # 每次調(diào)整該節(jié)點(diǎn)使得滿足最大堆的要求
    for i in range((len(data) >> 1) - 1, -1, -1):
        adjustHeap(i, len(data))

    # 從構(gòu)建好的最大堆取出堆頂元素(也就是最大值)，然后放到數(shù)組末尾(即將這個(gè)節(jié)點(diǎn)刪除)
    # 刪除之后需要重新調(diào)整堆的結(jié)構(gòu)以滿足最大堆的定義。
    # 由于上一步已經(jīng)構(gòu)建了一個(gè)最大堆，因此這里只需要對(duì)新的根節(jié)點(diǎn)的元素進(jìn)行調(diào)整即可
    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()