目錄

1.冒泡排序
2.選擇排序
3.插入排序
4.堆排序
5.歸并排序
6.快速排序
7.希爾排序

一個比較：比快多少？
假設(shè)n=100000; =;=1660964;前者約是后者的6000倍；約等于一分鐘和4天的比例；
這個比較是為了說明兩種復(fù)雜度算法的差異之大；更說明了學(xué)習(xí)更有效率算法的必要性

排序算法可針對數(shù)字類型，字符，或者更高級的類型進行排序，算法邏輯都是一樣的僅僅比較邏輯做策略模式替換即可。
以下所有代碼案例，僅進行數(shù)字類型排序

一，冒泡排序

原理：遍歷數(shù)列，每個過程，比較當(dāng)前值與下一位置的值，通過交換位置，將較大的數(shù)置后；像冒泡一樣
總的比較次數(shù)為（n-1）+（n-2）+…+1≈。復(fù)雜度為

# code utf-8
def up_sort(lis:list, n:int):
    for i in range(n):
        for j in range(0, n-i-1):
            if lis[j] < lis[j+1]:
               lis[j], lis[j+1] = lis[j+1], lis[j]
               print(lis) # 通過這一行打印排序步驟，直接看到冒泡效果

a = [i for i in range(10)]
a.reverse()

print(a)  # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
up_sort(a, len(a))
print(a)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

二，選擇排序

原理：從左至右（or從上到下）遍歷，尋找遍歷最小值，放在數(shù)列最左端；遞歸；
總的比較次數(shù)為（n-1）+（n-2）+…+1≈。復(fù)雜度為

# code utf-8
def selec_sort(lis:list, n:int):
    for i in range(n):
        # 尋找i~n區(qū)間的最小值
        min_index = i
        for j in range(i+1, n):
            if lis[j] < lis[min_index]:
                min_index = j
        # swap函數(shù)交換位置，如果是C++ 11以上版本，std中即包含swap
        lis[i], lis[min_index] = lis[min_index], lis[i]

a = [i for i in range(10)]
a.reverse()

print(a)  # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
selec_sort(a, len(a))
print(a)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

三，插入排序（?? 有應(yīng)用價值）

插入排序，是優(yōu)化版的冒泡排序，在于提前終止循環(huán)，節(jié)省資源；排序目標(biāo)有序性越高，插入排序的性能就越優(yōu)于冒泡和選擇
原理：從左至右（or從上到下）遍歷，將當(dāng)前值，插入到左端已排序序列的合適位置；
總的比較次數(shù)為（n-1）+（n-2）+…+1≈。復(fù)雜度為
對于完全有序的數(shù)組，插入排序的復(fù)雜度為

# code utf-8
# 方法一：根據(jù)自己的理解寫的，把握好index的理解，否則容易出錯
def insert_sort(lis:list, n:int):   # 
    for i in range(1,n): # 最左側(cè)第一個數(shù)字不用排序，默認是已排序列
        for j in range(0, i):
            if lis[i] < lis[j]:
                a = lis[i]
                lis.remove(lis[i])
                lis.insert(j, a)
                break
        print(lis)

# 方法二：根據(jù)某教程
def insert_sort(lis:list, n:int):   # 借鑒
    for i in range(1,n): # 最左側(cè)第一個數(shù)字不用排序，默認是已排序列
        for j in range(i, 0, -1):
            if lis[j] < lis[j-1]:
                lis[j], lis[j-1] = lis[j-1], lis[j]
            else:
                break
        print(lis)

# 方法三，優(yōu)化
def insert_sort(lis:list, n:int):
    for i in range(1,n): # 最左側(cè)第一個數(shù)字不用排序，默認是已排序列
        temp = lis[i]
        target_index = i
        for j in range(i, 0, -1):
            if temp < lis[j-1]:
                lis[j] = lis[j-1] # 賦值代替交換
                target_index = j - 1 # 當(dāng)前位置
            else:
                break
        lis[target_index] = temp
        print(lis)

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    insert_sort(a, len(a))

按照原理和代碼的說明，可以看到，插入排序在迭代次數(shù)上，比較次數(shù)上，都要少于冒泡和選擇排序；
問題：但是實際測試運行時間，會發(fā)現(xiàn)選擇排序 優(yōu)于 插入排序 優(yōu)于 冒泡排序
原因：這是因為，選擇排序比較計算多，但是交換位置操作少，而插入排序和冒泡排序存在大量數(shù)組元素位置交換，操作內(nèi)存的IO時間開銷是很大的；

優(yōu)化思路：
1，使用方法一，只交換一次，（效率未測試）
2，使用方法三，通過賦值替代交換；此方法同樣可用于優(yōu)化冒泡排序（這樣優(yōu)化后，冒泡排序就變成了選擇排序）

四，堆排序

略

五，歸并排序一：自頂向下遞歸（先分組，后merge）（合并排序 merge_sort）

原理：將排序序列分半，兩組排序后再合并成有序序列。遞歸。
實現(xiàn)：上的細節(jié)就是：將序列無限二分，最終分為每組兩個元素的很多小組，小組內(nèi)排序后，兩個a級別小組合并排序為b界別，兩個b級別再繼續(xù)合并排序，直至合為一個有序的序列。
復(fù)雜度分析：由于是二分法分組，如果總元素是N個，那么序列分裂行為次數(shù)（即遞歸層數(shù)）級別的

核心算法->合并兩組有序序列邏輯：例如要歸并[4,6]，[3,7]兩個小組；
1，首先創(chuàng)建一個新的空數(shù)組lis_new
2，比較兩個序列首位，然后將較小的推入lis_new中。遞歸。
3，關(guān)鍵點：三個索引，兩個待合并小組當(dāng)前值的索引和新數(shù)組的索引(通過比較，賦值，移動索引，而不是刪除小組內(nèi)容，推入新數(shù)組這種有更大IO開銷的操作)
合并兩組序列的復(fù)雜度與序列元素個數(shù)有關(guān)，很簡單這個算法是的。
結(jié)合上面歸并算法的理解，歸并算法有兩部分，分裂：復(fù)雜度，合并：復(fù)雜度;
所以歸并排序的復(fù)雜度是的

歸并排序的缺點：占用內(nèi)存大，典型的空間換時間

以下代碼是我根據(jù)理解和參考自己實現(xiàn)的，雖然完成了示例中的排序，不保證完全正確。

# code utf-8
import math

def merge_lis(lis, i, j, mid):
    arr1 = [item for item in lis]
    index1, index2 = i, mid+1
    for k in range(j-i+1):
        if index1>mid:
            lis[k+i] = arr1[index2]
            index2 += 1
        elif index2>j:
            lis[k+i] = arr1[index1]
            index1 += 1
        elif arr1[index1] < arr1[index2]:
            lis[k+i] = arr1[index1]
            index1 += 1
        else:
            lis[k+i] = arr1[index2]
            index2 += 1

    print(lis)

def merge_sort(lis:list, n:int):
    def split(lis:list, i:int, j:int): # 要處理的數(shù)據(jù)段的開始位置，結(jié)束位置；前閉后閉
        if (i >= j):
            return
        # 第一步：數(shù)組二分
        mid = math.floor((i+j)/2)  # 存在數(shù)據(jù)過大，溢出風(fēng)險;向上取整
        split(lis, i, mid)
        split(lis, mid+1, j)
        # 第二步：merge兩段，排序核心
        merge_lis(lis, i, j, mid)

    split(lis, 0, n-1)

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    merge_sort(a, len(a))

思考：對于近乎有序的數(shù)組，歸并排序與插入排序效率比較如何？答案是插入排序更快，大概是倍，這從兩者的復(fù)雜度上就能計算得出，因為對于近乎有序的數(shù)組，優(yōu)化后的插入排序，復(fù)雜度是接近的。
優(yōu)化：
方法一：判斷。同樣的，對于歸并排序優(yōu)化后，對于近乎有序的數(shù)組，也可以是接近復(fù)雜度的，優(yōu)化方法，僅需增加一行代碼；如下代碼示例 （提升效率數(shù)十倍，當(dāng)n=50000）
方法二：結(jié)合。當(dāng)歸并遞歸到底的時候（分組足夠小的時候，比如每組元素少于10個），此時可使用插入排序來提高性能。（提升效率一倍，當(dāng)n=50000）

# 只需在上面的程序基礎(chǔ)上，增加一行；僅對于無序的進行歸并，有序的不歸并
if lis[mid] > lis[mid+1]:  
     merge_lis(lis, i, j, mid)

五，歸并排序二（自底向上，迭代）

原理不變，優(yōu)化方式相同；僅邏輯相反；

#此部分由于python的循環(huán)語法限制，不易實現(xiàn)，后面補C++實現(xiàn)

六，快速排序

原理：隨機選一個數(shù)作為基準(zhǔn)；將其余的數(shù)字與基準(zhǔn)比較，分為比基準(zhǔn)大和比基準(zhǔn)小的兩組；遞歸即可。
。平均復(fù)雜度為，如果運氣較差，每次都選最小值為基準(zhǔn)，復(fù)雜度為，本質(zhì)同選擇排序
關(guān)鍵：如何分出兩組，并找出基準(zhǔn)值的合理索引值。

1，基礎(chǔ)版(效率即優(yōu)于歸并)

# 第一版，原理實現(xiàn)
def partation(lis, start, end):
    p = lis[start]
    p_index = start
    for i in range(start+1, end+1):
        if lis[i] < p:
            lis[i], lis[p_index+1] = lis[p_index+1], lis[i]# 較小的數(shù)swap到前面
            p_index += 1 # 記錄正確索引位置
    lis[start], lis[p_index] = lis[p_index], lis[start]
    return p_index

def _quick_s(lis, start, end):
    if start > end:
        return
    index = partation(lis, start, end)  # 選擇基準(zhǔn)值，以基準(zhǔn)值分組，并返回基準(zhǔn)值索引
    _quick_s(lis, start, index-1)
    _quick_s(lis, index+1, end)

def quick_sort(lis:list, n:int):
    _quick_s(lis, 0, n-1)
    pass

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    quick_sort(a, len(a))
    print(a)

問題：
優(yōu)化：
2，隨機化，雙路，三路
3，其他問題

六，希爾排序（高級插入排序）

原理：
復(fù)雜度為