排序

(1) 冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端，

作為最簡單的排序演算法之一，冒泡排序給我的感覺就像 Abandon 在單詞書里出現的感覺一樣，每次都在第一頁第一位，所以最熟悉，冒泡排序還有一種優化演算法，就是立一個 flag，當在一趟序列遍歷中元素沒有發生交換，則證明該序列已經有序，但這種改進對于提升性能來

說并沒有什么太大作用，

1. 演算法步驟

比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，

對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，

針對所有的元素重復以上的步驟，除了最后一個，

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

2. 動圖演示

3. 什么時候最快

當輸入的資料已經是正序時（都已經是正序了，我還要你冒泡排序有何用啊），

4. 什么時候最慢

當輸入的資料是反序時（寫一個 for 回圈反序輸出資料不就行了，干嘛要用你冒泡排序呢，我是閑的嗎），

6. Python 代碼實作

def buddle_sort(li):
    flag = True
    for i in range(len(li) - 1):
        flag = False
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                flag = True
        if not flag:
            break
        print(f"第{i + 1}輪排序結果為{li}")


li = [9, 1, 5, 8, 3, 7, 4, 6, 2]
print(f"待排序列為：{li}")
buddle_sort(li)

運行結果：

待排序列為：[9, 1, 5, 8, 3, 7, 4, 6, 2]
第1輪排序結果為[1, 5, 8, 3, 7, 4, 6, 2, 9]
第2輪排序結果為[1, 5, 3, 7, 4, 6, 2, 8, 9]
第3輪排序結果為[1, 3, 5, 4, 6, 2, 7, 8, 9]
第4輪排序結果為[1, 3, 4, 5, 2, 6, 7, 8, 9]
第5輪排序結果為[1, 3, 4, 2, 5, 6, 7, 8, 9]
第6輪排序結果為[1, 3, 2, 4, 5, 6, 7, 8, 9]
第7輪排序結果為[1, 2, 3, 4, 5, 6, 7, 8, 9]

時間復雜度：O(n²)

(2) 選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序演算法，它的作業原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到所有元素均排序完畢，

python代碼實作：

def select_sort(li):
    for i in range(len(li)):
        min_num = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_num]:
                min_num = j
        if i != min_num:
            li[i], li[min_num] = li[min_num], li[i]
        print(f"第{i + 1}輪排序結果為{li}")


li = [9, 1, 5, 8, 3, 7, 4, 6, 2]
print(f"待排序列為：{li}")
select_sort(li)

運行結果：

待排序列為：[9, 1, 5, 8, 3, 7, 4, 6, 2]
第1輪排序結果為[1, 9, 5, 8, 3, 7, 4, 6, 2]
第2輪排序結果為[1, 2, 5, 8, 3, 7, 4, 6, 9]
第3輪排序結果為[1, 2, 3, 8, 5, 7, 4, 6, 9]
第4輪排序結果為[1, 2, 3, 4, 5, 7, 8, 6, 9]
第5輪排序結果為[1, 2, 3, 4, 5, 7, 8, 6, 9]
第6輪排序結果為[1, 2, 3, 4, 5, 6, 8, 7, 9]
第7輪排序結果為[1, 2, 3, 4, 5, 6, 7, 8, 9]
第8輪排序結果為[1, 2, 3, 4, 5, 6, 7, 8, 9]
第9輪排序結果為[1, 2, 3, 4, 5, 6, 7, 8, 9]

時間復雜度：O(n²)

(3) 插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法，它的作業原理是通過構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入，

python代碼實作：

def insert_sort(li):
    for i in range(1, len(li)):
        temp = li[i]
        j = i - 1
        while j >= 0 and li[j] > temp:
            li[j + 1] = li[j]
            j -= 1

        li[j + 1] = temp
        print(f"第{i}輪排序結果為{li}")


li = [9, 1, 5, 8, 3, 7, 4, 6, 2]
print(f"待排序列為：{li}")
insert_sort(li)

運行結果：

待排序列為：[9, 1, 5, 8, 3, 7, 4, 6, 2]
第1輪排序結果為[1, 9, 5, 8, 3, 7, 4, 6, 2]
第2輪排序結果為[1, 5, 9, 8, 3, 7, 4, 6, 2]
第3輪排序結果為[1, 5, 8, 9, 3, 7, 4, 6, 2]
第4輪排序結果為[1, 3, 5, 8, 9, 7, 4, 6, 2]
第5輪排序結果為[1, 3, 5, 7, 8, 9, 4, 6, 2]
第6輪排序結果為[1, 3, 4, 5, 7, 8, 9, 6, 2]
第7輪排序結果為[1, 3, 4, 5, 6, 7, 8, 9, 2]
第8輪排序結果為[1, 2, 3, 4, 5, 6, 7, 8, 9]

時間復雜度：O(n²)

(4) 希爾排序

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序，

python代碼實作：

def ShellSort(li):
    n = len(li)
    increment = int(n / 2)
    while increment > 0:
        for i in range(increment, n):
            temp = li[i]
            j = i
            while j >= increment and temp < li[j-increment]:
                li[j] = li[j - increment]
                j -= increment
            li[j] = temp
        increment = int(increment / 2)


if __name__ == '__main__':
    li = [9, 1, 5, 8, 3, 7, 4, 6, 2]
    print(f"待排序列為：{li}")
    ShellSort(li)
    print(f"排序后的序列為{li}")

運行結果：

待排序列為：[9, 1, 5, 8, 3, 7, 4, 6, 2]
排序后的序列為[1, 2, 3, 4, 5, 6, 7, 8, 9]

時間復雜度：O(nlogn)

(5) 堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點，堆排序可以說是一種利用堆的概念來排序的選擇排序，

python代碼實作：

import random


def shift(li, low, high):
    """
    :param li:串列
    :param low:堆的根節點位置
    :param high:堆的最后一個元素
    :return:
    """
    i = low  # 最開始指向根節點
    j = 2 * i + 1  # 開始是左孩子
    temp = li[low]  # 把堆頂存起來
    while j <= high:  # 只要j位置有數
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果存在右孩子并且比較大
            j = j + 1  # j指向右孩子
        if li[j] > temp:
            li[i] = li[j]
            i = j  # 往下看一層
            j = 2 * i + 1
        else:  # temp更大，把temp放到i的位置上
            li[i] = temp
            break
    else:
        li[i] = temp  # 把temp放到葉子節點上


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        # i表示建堆的時候調整部分的根的下標
        shift(li, i, n - 1)
    # 建堆完成
    print(f"所建的堆為：{li}")
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        shift(li, 0, i - 1)
    print(f"排序結果為：{li}")


if __name__ == '__main__':
    li = [i for i in range(10)]
    random.shuffle(li)
    print(f"待排序列為：{li}")
    heap_sort(li)

運行結果：

待排序列為：[4, 8, 9, 5, 2, 3, 1, 7, 0, 6]
所建的堆為：[9, 8, 4, 7, 6, 3, 1, 5, 0, 2]
排序結果為：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

此處用到了完全二叉樹的性質，不知道的話可以去了解一下，這里不再說明，

時間復雜度：O(nlogn)

(6) 歸并排序

歸并排序（英語：Merge sort，或mergesort），是創建在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，

分治法:

• 分割：遞回地把當前序列平均分割成兩半，
• 集成：在保持元素順序的同時將上一步得到的子序列集成到一起（歸并），

python代碼實作：

def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)

    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists) // 2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)


if __name__ == '__main__':
    a = [9, 1, 5, 8, 3, 7, 4, 6, 2]
    print(merge_sort(a))

運行結果：

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

時間復雜度：O(nlogn)

(7) 快速排序

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然后遞回地排序兩個子序列，

步驟為：

• 挑選基準值：從數列中挑出一個元素，稱為"基準"（pivot）;
• 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數可以到任何一邊），在這個分割結束之后，對基準值的排序就已經完成;
• 遞回排序子序列：遞回地將小于基準值元素的子序列和大于基準值元素的子序列排序，

遞回到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序，

選取基準值有數種具體方法，此選取方法對排序的時間性能有決定性影響，

python代碼實作：

def partition(li, left, right):
    temp = li[left]
    while left < right:
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        print(li)
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
        print(li)
    li[left] = temp
    print(li)
    return left


def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)


li = [5, 3, 7, 1, 2, 4, 9, 6, 8, 10]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)

運行結果：

[5, 3, 7, 1, 2, 4, 9, 6, 8, 10]
[4, 3, 7, 1, 2, 4, 9, 6, 8, 10]
[4, 3, 7, 1, 2, 7, 9, 6, 8, 10]
[4, 3, 2, 1, 2, 7, 9, 6, 8, 10]
[4, 3, 2, 1, 2, 7, 9, 6, 8, 10]
[4, 3, 2, 1, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 1, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 1, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 3, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 2, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 2, 2, 4, 5, 7, 9, 6, 8, 10]
[1, 2, 3, 4, 5, 7, 9, 6, 8, 10]
[1, 2, 3, 4, 5, 6, 9, 6, 8, 10]
[1, 2, 3, 4, 5, 6, 9, 9, 8, 10]
[1, 2, 3, 4, 5, 6, 9, 9, 8, 10]
[1, 2, 3, 4, 5, 6, 9, 9, 8, 10]
[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 8, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 8, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

時間復雜度：最優情況下O(nlogn),最壞情況下O(n²)

標籤：其他

上一篇：Unreal NetMode&NetRole 決議

下一篇：抓包工具 Charles 使用手冊