摘要：本篇主要實(shí)現(xiàn)九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計(jì)數(shù)排序。希爾排序是非穩(wěn)定排序算法。歸并排序算法依賴歸并操作。但是，計(jì)數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。

本篇主要實(shí)現(xiàn)九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計(jì)數(shù)排序。希望大家回顧知識(shí)的時(shí)候也能從我的這篇文章得到幫助。

為了防止誤導(dǎo)讀者，本文所有概念性內(nèi)容均截取自對(duì)應(yīng)Wiki

冒泡排序(Bubble Sort)是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

冒泡排序算法的運(yùn)作如下：

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

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

def bubble_sort(list):
    length = len(list)
    # 第一級(jí)遍歷
    for index in range(length):
        # 第二級(jí)遍歷
        for j in range(1, length - index):
            if list[j - 1] > list[j]:
                # 交換兩者數(shù)據(jù)，這里沒用temp是因?yàn)閜ython 特性元組。
                list[j - 1], list[j] = list[j], list[j - 1]
    return list

這種排序其實(shí)還可以稍微優(yōu)化一下，添加一個(gè)標(biāo)記，在排序已完成時(shí)，停止排序。

def bubble_sort_flag(list):
    length = len(list)
    for index in range(length):
        # 標(biāo)志位
        flag = True
        for j in range(1, length - index):
            if list[j - 1] > list[j]:
                list[j - 1], list[j] = list[j], list[j - 1]
                flag = False
        if flag:
            # 沒有發(fā)生交換，直接返回list
            return list
    return list

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理大致是將后面的元素最小元素一個(gè)個(gè)取出然后按順序放置。

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，

再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

def selection_sort(list):
   n=len(list)
   for i in range (0,n):
       min = i
       for j in range(i+1,n):
           if list[j]
插入排序
原理
插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
步驟

從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5

代碼
def insert_sort(list):
    n = len(list)
    for i in range(1, n):
        # 后一個(gè)元素和前一個(gè)元素比較
        # 如果比前一個(gè)小
        if list[i] < list[i - 1]:
            # 將這個(gè)數(shù)取出
            temp = list[i]
            # 保存下標(biāo)
            index = i
            # 從后往前依次比較每個(gè)元素
            for j in range(i - 1, -1, -1):
                # 和比取出元素大的元素交換
                if list[j] > temp:
                    list[j + 1] = list[j]
                    index = j
                else:
                    break
            # 插入元素
            list[index] = temp
    return list
希爾排序
原理
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
步驟
每次以一定步長(就是跳過等距的數(shù))進(jìn)行排序，直至步長為1.
代碼
def shell_sort(list):
    n = len(list)
    # 初始步長
    gap = round(n / 2)
    while gap > 0:
        for i in range(gap, n):
            # 每個(gè)步長進(jìn)行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步長
        gap = round(gap / 2)
    return list
步長使用的是Donald Shell的建議，另外步長還可以使用Sedgewick提出的(1, 5, 19, 41, 109,...)。
也可以使用斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分區(qū)比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列。
歸并排序
原理
歸并操作(歸并算法)，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。歸并排序算法依賴歸并操作。
步驟
迭代法

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾

遞歸法
假設(shè)序列共有n個(gè)元素：

將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 {displaystyle floor(n/2)} floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素
將上述序列再次歸并，形成 {displaystyle floor(n/4)} floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素
重復(fù)步驟2，直到所有元素排序完畢

代碼
# 遞歸法
def merge_sort(list):
    # 認(rèn)為長度不大于1的數(shù)列是有序的
    if len(list) <= 1:
        return list
    # 二分列表
    middle = len(list) // 2
    left = merge_sort(list[:middle])
    right = merge_sort(list[middle:])
    # 最后一次合并
    return merge(left, right)
# 合并
def merge(left, right):
    l,r=0,0
    result=[]
    while l
鄙人不才，不知?dú)w并排序的迭代法如何用Python實(shí)現(xiàn)，望指教。
快速排序
原理
快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。
步驟

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

代碼
普通版
def quick_sort(list):
    less = []
    pivotList = []
    more = []
    # 遞歸出口
    if len(list) <= 1:
        return list
    else:
        # 將第一個(gè)值做為基準(zhǔn)
        pivot = list[0]
        for i in list:
            # 將比急轉(zhuǎn)小的值放到less數(shù)列
            if i < pivot:
                less.append(i)
            # 將比基準(zhǔn)打的值放到more數(shù)列
            elif i > pivot:
                more.append(i)
            # 將和基準(zhǔn)相同的值保存在基準(zhǔn)數(shù)列
            else:
                pivotList.append(i)
        # 對(duì)less數(shù)列和more數(shù)列繼續(xù)進(jìn)行排序
        less = quick_sort(less)
        more = quick_sort(more)
        return less + pivotList + more
咳咳，下面這段代碼出自《Python cookbook 第二版》傳說中的三行實(shí)現(xiàn)python快速排序。
def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + 
               [pivot] + 
               qsort([x for x in arr[1:] if x >= pivot])
當(dāng)然還有一行語法糖版本:
qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]
是不是感受到了Python的魅力？
堆排序
原理
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
步驟

創(chuàng)建最大堆:將堆所有數(shù)據(jù)重新排序，使其成為最大堆
最大堆調(diào)整:作用是保持最大堆的性質(zhì)，是創(chuàng)建最大堆的核心子程序
堆排序:移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

代碼
def heap_sort(list):
    # 創(chuàng)建最大堆
    for start in range((len(list) - 2) // 2, -1, -1):
        sift_down(list, start, len(list) - 1)

    # 堆排序
    for end in range(len(list) - 1, 0, -1):
        list[0], list[end] = list[end], list[0]
        sift_down(list, 0, end - 1)
    return list


# 最大堆調(diào)整
def sift_down(lst, start, end):
    root = start
    while True:
        child = 2 * root + 1
        if child > end:
            break
        if child + 1 <= end and lst[child] < lst[child + 1]:
            child += 1
        if lst[root] < lst[child]:
            lst[root], lst[child] = lst[child], lst[root]
            root = child
        else:
            break
計(jì)數(shù)排序
原理
當(dāng)輸入的元素是n個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。例如：計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。
步驟

找出待排序的數(shù)組中最大和最小的元素
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

代碼
def count_sort(list):
    min = 2147483647
    max = 0
    # 取得最大值和最小值
    for x in list:
        if x < min:
            min = x
        if x > max:
            max = x
    # 創(chuàng)建數(shù)組C
    count = [0] * (max - min +1)
    for index in list:
        count[index - min] += 1
    index = 0
    # 填值
    for a in range(max - min+1):
        for c in range(count[a]):
            list[index] = a + min
            index += 1
    return list
第九種排序
None？
當(dāng)然不會(huì)
自然就是系統(tǒng)自帶的
list.sort()
以上所有源代碼均在Github共享希望與大家共同進(jìn)步!
參考資料

維基百科: 冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序、堆排序、計(jì)數(shù)排序

Python Cookbook

感謝
知乎用戶:dhx1793516813、左鳶、靈劍
為本文缺漏之處提出建議
EOF
轉(zhuǎn)載請(qǐng)注明出處：http://eindex.me/post/base-so...
訪問原文「基本排序算法的Python實(shí)現(xiàn)」獲取最佳閱讀體驗(yàn)并參與討論