GitHub：https://github.com/Pgrammerybj （進去的動動小手點個贊哈）

什么是算法？

我們舉一個可能不太恰當?shù)睦樱?/p>

如果將最終寫好運行的程序比作戰(zhàn)場，我們碼農(nóng)便是指揮作戰(zhàn)的將軍，而我們所寫的代碼便是士兵和武器。

那么數(shù)據(jù)結(jié)構(gòu)和算法是什么？答曰：兵法！

我們可以不看兵法在戰(zhàn)場上肉搏，如此，可能會勝利，可能會失敗。即使勝利，可能也會付出巨大的代價。我們寫程序亦然：沒有看過數(shù)據(jù)結(jié)構(gòu)和算法，有時面對問題可能會沒有任何思路，不知如何下手去解決；大部分時間可能解決了問題，可是對程序運行的效率和開銷沒有意識，性能低下；有時會借助別人開發(fā)的利器暫時解決了問題，可是遇到性能瓶頸的時候，又不知該如何進行針對性的優(yōu)化。

如果我們?？幢ǎ憧勺龅叫赜谐芍?，有時會事半功倍！同樣，如果我們常看數(shù)據(jù)結(jié)構(gòu)與算法，我們寫程序時也能游刃有余、明察秋毫，遇到問題時亦能入木三分、迎刃而解。

故，數(shù)據(jù)結(jié)構(gòu)和算法是一名程序開發(fā)人員的必備基本功，不是一朝一夕就能練成絕世高手的。冰凍三尺非一日之寒，需要我們平時不斷的主動去學習積累。

在這里將通過以下幾個排序算法來演示：
* 冒泡排序
* 選擇排序
* 插入排序
* 希爾排序
* 快速排序
* 歸并排序

分類演說

一、冒泡排序

1.冒泡排序算法的運作如下:

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

2.交換過程圖解:

冒泡排序

3.時間復雜度

• 最優(yōu)時間復雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束。）
• 最壞時間復雜度：O(n2)
• 穩(wěn)定性：穩(wěn)定

4.代碼演示：

def bubble_sort1(numList):
    """冒泡排序(正向，從前到后排,時間復雜度O(n2))"""
    length = len(numList)
    for i in range(0, length - 1):

        for j in range(0, length - 1 - i):

            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]


def bubble_sort2(numList):
    """冒泡排序(反向，從后往前排，時間復雜度O(n2))"""
    length = len(numList)
    for i in range(length - 1, 0, -1):

        for j in range(i):

            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]


def bubble_sort3(numList):
    """冒泡排序(如果給出的列表就是有序的序列，那么可以這樣優(yōu)化,時間復雜度O(n2)，最優(yōu)為O(n))"""
    length = len(numList)
    for i in range(length - 1, 0, -1):
        is_change = False
        for j in range(i):
            if numList[j] > numList[j + 1]:
                numList[j], numList[j + 1] = numList[j + 1], numList[j]
                is_change = True

        if not is_change:
            return


if __name__ == '__main__':
    li = [23, 23, 97, 1, 45, 775, 9, 12]
    li2 = [2, 1, 97, 324, 45, 775, 0, 12]
    li3 = [1, 2, 3, 4, 5, 6, 7, 8]
    li4 = [2, 1, 97, 324, 45, 775, 0, 12]

    print("排序前：" + str(li))
    bubble_sort1(li)
    print("正向排序" + str(li))

    print("排序前：" + str(li2))
    bubble_sort2(li2)
    print("反向排序" + str(li2))

    print("排序前：" + str(li3))
    bubble_sort3(li3)
    print("優(yōu)化排序" + str(li3))

    print("排序前：" + str(li4))
    bubble_sort3(li4)
    print("優(yōu)化排序" + str(li4))

二、選擇排序

1.選擇排序的原理

• 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/li>
• 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀?然后放到已排序序列的末尾。
• 以此類推，直到所有元素均排序完畢。

2.排序過程圖解:

選擇排序

3.時間復雜度

• 最優(yōu)時間復雜度：O(n2)
• 最壞時間復雜度：O(n2)
• 穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）

4.代碼演示：

def select_sort(numList):
    length = len(numList)

    for i in range(length - 1):

        minIndex = i

        for j in range(i + 1, length):

            if numList[minIndex] > numList[j]:
                minIndex = j

        numList[i], numList[minIndex] = numList[minIndex], numList[i]
        print("排序過程中：" + str(li))


if __name__ == '__main__':
    li = [23, 23, 97, 1, 45, 775, 9, 12]
    print("排序前：" + str(li))
    select_sort(li)
    print("排序后：" + str(li)

三、插入排序

1.插入排序算法的運作如下:

它是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

2.排序過程圖解:

插入排序

3.時間復雜度

• 最優(yōu)時間復雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
• 最壞時間復雜度：O(n2)
• 穩(wěn)定性：穩(wěn)定

4.代碼演示：

def insert_sort(numList):
length = len(numList)

for i in range(1, length):

    # for j in range(0, i):
    #
    #     if numList[i] < numList[j]:
    #         numList[i], numList[j] = numList[j], numList[i]

    for j in range(i, 0, -1):

        if numList[j] < numList[j - 1]:
            numList[j], numList[j - 1] = numList[j - 1], numList[j]
        else:
            break


if __name__ == '__main__':

li = [23, 23, 97, 1, 45, 775, 9, 12]
print("插入排序：")
print("排序前：" + str(li))
insert_sort(li)
print("排序后：" + str(li))

四、歸并排序

1.歸并排序的原理

歸并排序是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
將數(shù)組分解最小之后，然后合并兩個有序數(shù)組，基本思路是比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應的指針就往后移一位。然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復制過來即可。

2.排序過程圖解

歸并排序

3.時間復雜度

• 最優(yōu)時間復雜度：O(nlogn)
• 最壞時間復雜度：O(nlogn)
• 穩(wěn)定性：穩(wěn)定

4.代碼演示

def merge_sort(numlist):
    # 1.獲取到需要排序的隊列

    length = len(numlist)

    # 2.判斷列表的長度，如果為1則不需排序直接返回

    if length <= 1:
        return numlist

    # 3.獲取中間點，將隊列的元素分成兩個部分，遞歸繼續(xù)拆分

    center_point = length // 2

    # 拆分的左邊的部分
    left_list = merge_sort(numlist[:center_point])

    # 拆分的右邊的部分，繼續(xù)遞歸，直至隊列的元素為1
    right_list = merge_sort(numlist[center_point:])

    # 4.初始化兩個控制點,和存放排序后的隊列
    left_point, right_point = 0, 0
    result = []

    # 5.循環(huán)比較左右兩側(cè)對應角標的元素大小
    while left_point < len(left_list) and right_point < len(right_list):

        # 左邊的元素和右邊的元素相比較，將小的元素添加棟隊列中
        if left_list[left_point] <= right_list[right_point]:
            result.append(left_list[left_point])
            left_point += 1
        else:
            result.append(right_list[right_point])
            right_point += 1

    # 當退出上面的while循環(huán)就說明左側(cè)或者右側(cè)有一方的元素已經(jīng)全部取完了，此時如果另一方如果還有元素那么就將剩余的元素添加到result中
    result += left_list[left_point:]
    result += right_list[right_point:]

    # 6.返回排序后的隊列給用戶
    return result


if __name__ == '__main__':
    num_list = [12, 87, 9, 6, 2, 876, 12, 0, 4]

    print("排序前：" + str(num_list))

    sortList = merge_sort(num_list)

    print("排序后：" + str(sortList))

持續(xù)更新....

喜歡的朋友動動小手點個贊咯，我會繼續(xù)更新相關(guān)的內(nèi)容，還望多多支持。

GitHub：https://github.com/Pgrammerybj （進去的動動小手點個贊哈）