摘要：創建最大堆堆排序八計數排序以上節選自維基百科代碼如下為數組中的最大值待排序數組長度設置輸出序列，初始化為設置技術序列，初始化為本文章參考維基百科和八大排序算法實現合輯

一、冒泡排序

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

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

代碼實現：

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）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

以上節選自維基百科

代碼實現：

def findSmallest(arr):  # 用于查找出數組中最小的元素，返回最小元素的索引。
    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

三、插入排序

步驟如下

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

代碼實現

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

四、希爾排序

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

以上節選自維基百科

代碼實現：

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

五、歸并排序

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

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

代碼如下：

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)

六、快速排序

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

以上節選自維基百科

代碼如下：

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)

七、堆排序

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

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

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
    
# 創建最大堆
    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

八、計數排序
以上節選自維基百科
代碼如下：

def counting_sort(numberlist, maxnumber):  # maxnumber為數組中的最大值
    length = len(numberlist)  # 待排序數組長度
    b = [0 for i in range(length)] # 設置輸出序列，初始化為0
    c = [0 for i in range(maxnumber+ 1)]  # 設置技術序列，初始化為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實現合輯