一、冒泡排序

冒泡排序算法的運作如下：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
針對所有的元素重復(fù)以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
以上節(jié)選自維基百科

代碼實現(xiàn)：

          
            def bubble_sort(numberlist):
    length = len(numberlist)
    for i in range(length):
        for j in range(1, length - i):
            if numberlist[j - 1] > numberlist[j]:
                numberlist[j], numberlist[j - 1] = numberlist[j - 1], numberlist[j]
    return numberlist
          
        

二、選擇排序

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

以上節(jié)選自維基百科

代碼實現(xiàn)：

          
            def findSmallest(arr):  # 用于查找出數(shù)組中最小的元素，返回最小元素的索引。
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if smallest > arr[i]:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectSort(arr):
    newArr = []
    while arr:
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr



          
        

三、插入排序

步驟如下

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

代碼實現(xiàn)

          
            def insert_sort(data):
    for k in range(1, len(data)):
        cur = data[k]
        j = k
        while j > 0 and data[j - 1] > cur:
            data[j] = data[j - 1]
            j -= 1
        data[j] = cur
    return data

          
        

四、希爾排序

希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來越小的步長進(jìn)行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。

以上節(jié)選自維基百科

代碼實現(xiàn)：

          
            def shell_sort(numberlist):
    length = len(numberlist)
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            temp = numberlist[i]
            j = i
            while j >= gap and numberlist[j - gap] > temp:
                numberlist[j] = numberlist[j - gap]
                j -= gap
            numberlist[j] = temp
        gap = gap // 2
    return numberlist
          
        

五、歸并排序

原理如下（假設(shè)序列共有{displaystyle n}個元素）：

將序列每相鄰兩個數(shù)字進(jìn)行歸并操作，形成{displaystyle ceil(n/2)}個序列，排序后每個序列包含兩/一個元素
若此時序列數(shù)不是1個則將上述序列再次歸并，形成{displaystyle ceil(n/4)}個序列，每個序列包含四/三個元素
重復(fù)步驟2，直到所有元素排序完畢，即序列數(shù)為1
以上節(jié)選自維基百科

代碼如下：

          
            def  merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result


def merge_sort(numberlist):
    if len(numberlist) <= 1:
        return numberlist
    mid = len(numberlist) // 2
    left = numberlist[:mid]
    right = numberlist[mid:]

    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)
          
        

六、快速排序

從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”（pivot），
重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個分割結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分割（partition）操作。
遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

以上節(jié)選自維基百科

代碼如下：

          
            def quick_sort(array):
        if len(array) < 2:
            return array
        else:
            pivot = array[0]
            less = [i for i in array[1:] if i <= pivot]
            greater = [i for i in array[1:] if i > pivot]
            return quick_sort(less) + [pivot] + quick_sort(greater)
          
        

七、堆排序

若以升序排序說明，把數(shù)組轉(zhuǎn)換成最大堆積(Max-Heap Heap)，這是一種滿足最大堆積性質(zhì)(Max-Heap Property)的二叉樹：對于除了根之外的每個節(jié)點i, A[parent(i)] ≥ A[i]。

重復(fù)從最大堆積取出數(shù)值最大的結(jié)點(把根結(jié)點和最后一個結(jié)點交換，把交換后的最后一個結(jié)點移出堆)，并讓殘余的堆積維持最大堆積性質(zhì)。

          
            def heap_sort(numberlist):
    length = len(numberlist)
    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and numberlist[child] < numberlist[child + 1]:
                child += 1
            if numberlist[root] < numberlist[child]:
                numberlist[root], numberlist[child] = numberlist[child], numberlist[root]
                root = child
            else:
                break
    
# 創(chuàng)建最大堆
    for start in range((length - 2) // 2, -1, -1):
        sift_down(start, length - 1)

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

八、計數(shù)排序
以上節(jié)選自維基百科
代碼如下：

          
            def counting_sort(numberlist, maxnumber):  # maxnumber為數(shù)組中的最大值
    length = len(numberlist)  # 待排序數(shù)組長度
    b = [0 for i in range(length)] # 設(shè)置輸出序列，初始化為0
    c = [0 for i in range(maxnumber+ 1)]  # 設(shè)置技術(shù)序列，初始化為0
    for j in numberlist:
        c[j] = c[j] + 1
    for i in range(1, len(c)):
        c[i] = c[i] + c[i - 1]
    for j in numberlist:
        b[c[j] - 1] = j
        c[j] = c[j] - 1
    return b
          
        

本文章參考維基百科和八大排序算法python實現(xiàn)合輯