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

“排序算法可以說是數(shù)據(jù)結(jié)構(gòu)與算法當中最為基礎(chǔ)的部分”

1. 概述

排序算法可以說是數(shù)據(jù)結(jié)構(gòu)與算法當中最為基礎(chǔ)的部分，針對的是數(shù)組這一數(shù)據(jù)結(jié)構(gòu)。將數(shù)組中的無序數(shù)據(jù)元素通過算法整理為有序的數(shù)據(jù)元素即為排序。

2. 簡單排序

2.1 冒泡排序

簡介：

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

步驟如下：

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

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

3. 直到?jīng)]有任何一對數(shù)字需要比較時完成。

實現(xiàn)代碼：

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. 遍歷數(shù)組，找到最小的元素，將其置于數(shù)組起始位置。

2. 從上次最小元素存放的后一個元素開始遍歷至數(shù)組尾，將最小的元素置于開始處。

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

實現(xiàn)代碼：

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）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

步驟如下：

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序

2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描

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

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

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

6. 重復步驟2

實現(xiàn)代碼：

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)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。

步驟如下：

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

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

實現(xiàn)代碼：

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）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

步驟如下：

步驟：

1. 從數(shù)列中挑出一個元素，稱為 “基準”（pivot），

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

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

實現(xiàn)代碼：

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. 申請空間，創(chuàng)建兩個數(shù)組，長度分別為兩個有序數(shù)組的長度

2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置

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

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

5. 將另一序列剩下的所有元素直接復制到合并序列尾

實現(xiàn)代碼：

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

實現(xiàn)效果：

3.4 堆排序

簡介：

堆積排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆性質(zhì)：即子節(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

步驟如下：

1. 按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個過程稱為創(chuàng)建初始堆），交換R[0]和R[n]；

2. 將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1]；

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

實現(xiàn)代碼：

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/

喜歡，在看