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

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

1. 概述

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

2. 簡(jiǎn)單排序

2.1 冒泡排序

簡(jiǎn)介：

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

步驟如下：

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

2. 遍歷長(zhǎng)度減一，對(duì)剩下的元素從頭重復(fù)以上的步驟。

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

實(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 選擇排序

簡(jiǎn)介：

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

步驟如下：

1. 遍歷數(shù)組，找到最小的元素，將其置于數(shù)組起始位置。

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

3. 重復(fù)上述過(guò)程，直到元素排序完畢。

實(shí)現(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 插入排序

簡(jiǎn)介：

插入排序（Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

步驟如下：

1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

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

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

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

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

6. 重復(fù)步驟2

實(shí)現(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. 高級(jí)排序

3.1 希爾排序

簡(jiǎn)介：

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

步驟如下：

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

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

實(shí)現(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 快速排序

簡(jiǎn)介：

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

步驟如下：

步驟：

1. 從數(shù)列中挑出一個(gè)元素，稱(chēng)為 “基準(zhǔn)”（pivot），

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

3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(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 歸并排序

簡(jiǎn)介：

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

步驟如下：

1. 申請(qǐng)空間，創(chuàng)建兩個(gè)數(shù)組，長(zhǎng)度分別為兩個(gè)有序數(shù)組的長(zhǎng)度

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

3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

4. 重復(fù)步驟3直到某一指針達(dá)到序列尾

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

實(shí)現(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

實(shí)現(xiàn)效果：

3.4 堆排序

簡(jiǎn)介：

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

步驟如下：

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

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

3. 重復(fù)上述過(guò)程，直到交換了R[0]和R[1]為止。

實(shí)現(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. 各排序算法時(shí)間空間復(fù)雜度

source: https://davidwangtm.github.io/2016/03/28/seven_sort/

喜歡，在看