七種排序算法 冒泡，選擇，插入，希爾，快速，歸併，堆

“排序算法可以說是數據結構與算法當中最爲基礎的部分”

1. 概述

排序算法可以說是數據結構與算法當中最爲基礎的部分，針對的是數組這一數據結構。將數組中的無序數據元素通過算法整理爲有序的數據元素即爲排序。

2. 簡單排序

2.1 冒泡排序

簡介：

冒泡排序（Bubble Sort）是一種簡單的排序算法。它重複地訪問要排序的數列，將每次訪問的最大值 “浮” 到數組尾部。

步驟如下：

  1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個，直到把最大的元素放到數組尾部。

  2. 遍歷長度減一，對剩下的元素從頭重複以上的步驟。

  3. 直到沒有任何一對數字需要比較時完成。

實現代碼：

def bubbleSort(arr):
    for i in range(len(arr))[::-1]:
        for j in range(i):
            if arr[j] > arr[j + 1]:
                swap(arr[j], arr[j + 1])

效果圖：

2.2 選擇排序

簡介：

選擇排序(Selection sort) 是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，重複上述過程，直到所有元素均排序完畢。

步驟如下：

  1. 遍歷數組，找到最小的元素，將其置於數組起始位置。

  2. 從上次最小元素存放的後一個元素開始遍歷至數組尾，將最小的元素置於開始處。

  3. 重複上述過程，直到元素排序完畢。

實現代碼：

def selectSort(arr):
    for i in range(len(arr)):
        min = i
        for j in range(i, len(arr)):
            if arr[j] < arr[min]:
                min = j
        swap(arr[i], arr[min])

效果圖：

2.3 插入排序

簡介：

插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

步驟如下：

  1. 從第一個元素開始，該元素可以認爲已經被排序

  2. 取出下一個元素，在已經排序的元素序列中從後向前掃描

  3. 如果該元素（已排序）大於新元素，將該元素移到下一位置

  4. 重複步驟 3，直到找到已排序的元素小於或者等於新元素的位置

  5. 將新元素插入到該位置中

  6. 重複步驟 2

實現代碼：

def insertSort(arr):
    for i in range(len(arr)):
        tmp = arr[i]
        pre = i - 1
        while pre >= 0 and arr[pre] > tmp:
            arr[pre + 1] = arr[pre]
            pre -= 1
        arr[pre + 1] = tmp

3. 高級排序

3.1 希爾排序

簡介：

希爾排序(Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。

步驟如下：

  1. 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；

  2. 隨着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。

實現代碼：

def insertSort(arr):
    k = 1
    while k < len(arr) / 3:
        k = 3 * h + 1 //此處爲Knuth算法

    while k > 0:
        for i in range(k, len(arr)):
            tmp = arr[i]
            pre = i - k
            while pre >= 0 and arr[pre] > tmp:
                arr[pre + k] = arr[pre]
                pre -= k
            arr[pre + k] = tmp
        k = (k - 1) / 3

效果圖：

3.2 快速排序

簡介：

快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

步驟如下：

步驟：

  1. 從數列中挑出一個元素，稱爲 “基準”（pivot），

  2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱爲分區（partition）操作。

  3. 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

實現代碼：

def quickSort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quickSort(arr, low, pivot - 1)
        quickSort(arr, pivot + 1, high)

def partition(arr, low, high):
    pivot = arr[low]
    while low < high:
        while low < high and arr[high] >= pivot:
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] <= pivot:
            low += 1
        arr[high] = arr[low]
    arr[low] = pivot
    return low

效果圖：

3.3 歸併排序

簡介：

歸併排序(Merge Sort) 是建立在歸併操作上的一種有效的排序算法, 該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱爲二路歸併。

步驟如下：

  1. 申請空間，創建兩個數組，長度分別爲兩個有序數組的長度

  2. 設定兩個指針，最初位置分別爲兩個已經排序序列的起始位置

  3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置

  4. 重複步驟 3 直到某一指針達到序列尾

  5. 將另一序列剩下的所有元素直接複製到合併序列尾

實現代碼：

def mergeSort(arr, low, high):
    if low < high:
        mid = low + (high - low) / 2
        mergeSort(arr, low, mid)
        mergeSort(arr, mid + 1, high)
        return merge(arr, low, mid, high)

def merge(arr, low, mid, high):
    leftArr = arr[low : mid + 1]
    rightArr = arr[mid + 1 : high + 1]
    i, j, m = 0, 0, low
    while i < len(leftArr) and j < len(rightArr)：
        if leftArr[i] < rightArr[j]:
            arr[m] = leftArr[i]
            i += 1
        else:
            arr[m] = rightArr[j]
            j += 1
        m += 1
    while i < len(leftArr):
        arr[m] = leftArr[i]
        m += 1
        i += 1
    while j < len(rightArr):
        arr[m] = rightArr[j]
        m += 1
        j += 1

實現效果：

3.4 堆排序

簡介：

堆積排序（Heap Sort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。

步驟如下：

  1. 按堆的定義將數組 R[0..n] 調整爲堆（這個過程稱爲創建初始堆），交換 R[0] 和 R[n]；

  2. 將 R[0..n-1] 調整爲堆，交換 R[0] 和 R[n-1]；

  3. 重複上述過程，直到交換了 R[0] 和 R[1] 爲止。

實現代碼：

def heapSort(arr):
    for i in range(len(arr) / 2)[::-1]:
        heapAdjust(arr, i, len(arr) - 1)

    for i in range(len(arr) - 1)[::-1]:
        swap(arr[i], arr[0])
        heapAdjust(arr, 0, i)

def heapAdjust(arr, parent, length)：
    tmp = arr[parent]
    child = 2 * parent + 1
    while child < length:
        if child + 1 < length and arr[child + 1] > arr[child]:
            child += 1
        if arr[child] <= tmp:
            break
        arr[parent] = arr[child]
        parent = child
        child = 2 * parent + 1
    arr[parent] = tmp

效果圖：

4. 各排序算法時間空間複雜度

source: https://davidwangtm.github.io/2016/03/28/seven_sort/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vJ9qiTch8eUeizSZJXCCQw

猜你喜歡