python如何實現(xiàn)常用的五種排序算法詳解

更新時間：2021年08月09日 14:28:01 作者：Mr-Yang`

排序有很多種實現(xiàn)方法，比如冒泡排序、選擇排序、歸并排序、希爾排序、快速排序、插入排序、堆排序、基數(shù)排序等,這篇文章主要給大家介紹了關(guān)于python如何實現(xiàn)常用的五種排序算法,需要的朋友可以參考下

一、冒泡排序

原理：

比較相鄰的元素。如果第一個比第二個大就交換他們兩個
每一對相鄰元素做同樣的工作，直到結(jié)尾最后一對
每個元素都重復(fù)以上步驟，除了最后一個

第一步：

將亂序中的最大值找出，逐一移到序列最后的位置

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]


def bubble_sort(alist):
    # 找最大值的方式是通過對列表中的元素進(jìn)行兩兩比較，值大的元素逐步向后移動
    # 序列中有n個元素，兩兩比較的話，需要比較n-1次
    for i in range(len(alist) - 1):  # 循環(huán)n-1次，控制兩兩比較的次數(shù)
        if alist[i] > alist[i + 1]:
            # 如果前面的元素大于后面的元素，交換兩個元素的位置，否則不做任何操作
            alist[i], alist[i + 1] = alist[i + 1], alist[i]

    return alist


print(bubble_sort(alist))

# 輸出：最大值已經(jīng)移動到最右邊了
[3, 5, 2, 1, 6, 7, 8, 4, 9]

當(dāng)上述代碼已經(jīng)可以將序列中的最大值放置到合適的位置，然后我們就可以將上述操作繼續(xù)作用到 n-1 和元素對應(yīng)的新序列，則就可以將 n-1 個元素對應(yīng)的最大值放置到了 n-1 和元素的最后位置。

結(jié)論：發(fā)現(xiàn)如果將上述的操作逐步的作用 n-1 此就可以將整個序列變成有序的。

第二步：

將第一步的操作繼續(xù)作用 n-1 次

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]


def bubble_sort(alist):

    for j in range(len(alist)-1):   # 外層循環(huán)次數(shù)遞增，內(nèi)層循環(huán)次數(shù)遞減
        for i in range(len(alist) - 1-j):  # 循環(huán)次數(shù)需要遞減-j，控制兩兩比較的次數(shù)
            if alist[i] > alist[i + 1]:
                # 如果前面的元素大于后面的元素，交換兩個元素的位置，否則不做任何操作
                alist[i], alist[i + 1] = alist[i + 1], alist[i]

    return alist


print(bubble_sort(alist))

# 輸出
[1, 2, 3, 4, 5, 6, 7, 8, 9]

二、選擇排序

思路：

首先在序列中找到最大（小）元素，存放到序列的最后
在從剩余的序列元素中繼續(xù)找最大（小）的元素，放到序列中上一個最大值的前一個位置
重復(fù)第二步，直到所有元素排序完畢

第一步：

將亂序中的元素兩兩比較，找出最大值，然后直接將最大值放置到序列最后的位置（將最大值直接和最后一個元素交換位置）

def select_sort(alist):
    max_index = 0  # 最大值元素的下標(biāo)，一開始假設(shè)下標(biāo)為0的元素為最大值
    for i in range(len(alist) - 1):  # 循環(huán)控制兩兩比較的次數(shù)
        # 如果在比較的過程中發(fā)現(xiàn)，下標(biāo)為max_index不是最大值，那么就改變max_index
        if alist[max_index] < alist[i + 1]:
            max_index = i + 1

    # 循環(huán)結(jié)束后max_index就一定是最大值的下標(biāo)，并且把該數(shù)和最后一個值做交換
    alist[len(alist) - 1], alist[max_index] = alist[max_index], alist[len(alist) - 1]
    return alist


alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
print(select_sort(alist))

# 輸出
[3, 5, 4, 2, 1, 7, 8, 6, 9]

第二步：

將第一步繼續(xù)作用 n-1 次

def select_sort(alist):
    for j in range(len(alist) - 1):# 外層循環(huán)遞增n-1次
        max_index = 0  # 最大值元素的下標(biāo)，一開始假設(shè)下標(biāo)為0的元素為最大值
        for i in range(len(alist) - 1 - j):  # 內(nèi)層循環(huán)遞減，循環(huán)控制兩兩比較的次數(shù)
            # 如果在比較的過程中發(fā)現(xiàn)，下標(biāo)為max_index不是最大值，那么就改變max_index
            if alist[max_index] < alist[i + 1]:
                max_index = i + 1

        # 循環(huán)結(jié)束后max_index就一定是最大值的下標(biāo)，并且把該數(shù)和最后一個值做交換
        alist[len(alist) - 1 - j], alist[max_index] = alist[max_index], alist[len(alist) - 1 - j]
    return alist


alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
print(select_sort(alist))

三、插入排序

思路：

需要將原始序列分為兩個部分：有序部分、無序部分。
將無序部分中的元素逐一插入到有序部分中

注意：初始情況下，有序部分為亂序序列中的第一個元素，無序部分為亂序序列的 n-1 個元素

例如：

# 亂序序列：[8,3,5,7,6]
[8,    3,5,7,6] # 8就是初始的有序部分，3、5、7、6就是初始的無序部分
[3,8,    5,7,6]
[3,5,8,    7,6]
[3,5,7,8,    6]
[3,5,7,6,8,   ]

第一步：

定義一個變量 i ，i 表示的是有序部分元素的個數(shù)和無序部分第一個元素小標(biāo)

alist = [8, 3, 1, 6, 7]

i = 1  # i 就是有序部分元素的個數(shù)和無序部分第一個元素下標(biāo)
# alist[i-1]：有序部分最后一個元素下標(biāo)
# alist[i]：無序部分第一個元素下標(biāo)
if alist[i - 1] > alist[i]:
    alist[i], alist[i - 1] = alist[i - 1], alist[i]
 # [3, 8,    1, 6, 7]

第二步：循環(huán)作用到每個元素中

alist = [8, 3, 1, 6, 7]

i = 2
# alist[i-1]：有序部分最后一個元素下標(biāo)
# alist[i]：無序部分第一個元素下標(biāo)
while i > 0:
    if alist[i - 1] > alist[i]:
        # 循環(huán)第一次時[3,1,8,   6,7]
        alist[i], alist[i - 1] = alist[i - 1], alist[i]
        i -= 1
        # 循環(huán)繼續(xù)
        # [1,3,8,   6，7]
    else:
        break

第三步：

處理變量 i，需要讓 i 進(jìn)行自己遞增

for i in range(1, len(alist)): # i = [1,2,3,4]
    # alist[i-1]：有序部分最后一個元素下標(biāo)
    # alist[i]：無序部分第一個元素下標(biāo)
    while i > 0:
        if alist[i - 1] > alist[i]:
            alist[i], alist[i - 1] = alist[i - 1], alist[i]
            i -= 1
        else:
            break

完整代碼：

def insert_sort(alist):
    for i in range(1, len(alist)):
        while i > 0:
            if alist[i - 1] > alist[i]:
                alist[i - 1], alist[i] = alist[i], alist[i - 1]
                i -= 1
            else:
                break
    return alist

四、希爾排序

關(guān)鍵變量：增量gap

gap：初始值為 len(alist) // 2

表示分組的組數(shù)
每一組數(shù)據(jù)之間的間隔

插入排序就是增量為 1 的希爾排序

第一步：

將插入排序代碼寫出

def hill_sort(alist):
    for i in range(1, len(alist)):
        while i > 0:
            if alist[i - 1] > alist[i]:
                alist[i - 1], alist[i] = alist[i], alist[i - 1]
                i -= 1
            else:
                break
    return alist

第二步：

在插入排序代碼中加入增量的概念

def hill_sort(alist):
    gap = len(alist) // 2  # 初識增量
    
    # 將插入排序中的增量1替換成gap
    # 由增量1變成了增量為gap了
    for i in range(gap, len(alist)):
        while i > 0:
            if alist[i - gap] > alist[i]:
                alist[i - gap], alist[i] = alist[i], alist[i - gap]
                i -= gap
            else:
                break
    return alist

第三步：

在第二步中進(jìn)行增量的縮減（增量縮減到1結(jié)束）完整代碼

def hill_sort(alist):
    gap = len(alist) // 2  # 初識增量

    while gap >= 1:
        for i in range(gap, len(alist)):
            while i > 0:
                if alist[i - gap] > alist[i]:
                    alist[i - gap], alist[i] = alist[i], alist[i - gap]
                    i -= gap
                else:
                    break
        gap //= 2  # 縮減增量
    return alist

五、快速排序

思路：

將列表中第一個元素設(shè)定為基準(zhǔn)數(shù)字，賦值給mid變量，然后將整個列表中比基準(zhǔn)小的數(shù)值放在基準(zhǔn)的左側(cè)，比基準(zhǔn)大的數(shù)字放在基準(zhǔn)右側(cè)，然后將基準(zhǔn)數(shù)字左右兩側(cè)的序列在根據(jù)此方法進(jìn)行排放
定義兩個指針，low 指向最左側(cè)，high 指向最右側(cè)
然后對最右側(cè)指針進(jìn)行向左移動，移動法則是，如果指針指向的數(shù)值比基準(zhǔn)小，則將指針指向的數(shù)字移動到基準(zhǔn)數(shù)字原始位置，否則繼續(xù)移動指針。
如果最右側(cè)指針指向的數(shù)值移動到基準(zhǔn)位置時，開始移動最左側(cè)指針，將其向右移動，如果該指針指向的數(shù)值大于基準(zhǔn)側(cè)將該數(shù)值移動到最右側(cè)指針指向的位置，然后停止移動。
如果左右側(cè)指針重復(fù)則，將基準(zhǔn)放入左右指針重復(fù)的位置，則基準(zhǔn)左側(cè)為比其小的數(shù)值，右側(cè)為比其大的數(shù)值

第一步：

核心操作，將基數(shù) mid 放置到序列中間，使得基數(shù)左側(cè)都是比它小的，右側(cè)是比它大的

def quick_sort(alist):
    low = 0  # 第一個元素下標(biāo)
    high = len(alist) - 1  # 最后一個元素下標(biāo)

    mid = alist[low]  # 基數(shù)：初始值為序列中的第一個數(shù)值
    while low != high:
        # 先移動high
        while low < high:
            if mid < alist[high]:  # 下標(biāo)high對應(yīng)的值大于mid，high就向右偏移1
                high = high - 1
            else:
                # 否則，就把將high指向的數(shù)值放置到左側(cè)下標(biāo)為low對應(yīng)的空位
                alist[low] = alist[high]
                break  # 傳遞后high下標(biāo)偏移結(jié)束

        # 開始移動low
        while low < high:
            if mid > alist[low]:  # 下標(biāo)low對應(yīng)的值小于mid，low就向左偏移1
                low = low + 1
            else:
                # 否則，就把將low指向的數(shù)值放置到左側(cè)下標(biāo)為high對應(yīng)的空位
                alist[high] = alist[low]
                break  # 并結(jié)束
    # 最后當(dāng)low和high相等的時候，那么就把mid傳給下標(biāo)為low或high的位置
    alist[low] = mid
    return alist


alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
print(quick_sort(alist))

# 輸出——>6左邊都是比6小的，右邊都是比6大的
[5, 1, 2, 4, 3,    6,    9, 7, 10, 8]

第二步：

將第一步的核心操作遞歸作用到基數(shù)的左右兩側(cè)的子序列中

# 那么如何區(qū)分根據(jù)基數(shù)拆分出的左右子序列呢？可以通過傳入指定的left和right來指定不同的子序列
def quick_sort(alist, left, right):
    low = left  # 第一個元素下標(biāo)
    high = right  # 最后一個元素下標(biāo)

    if low > high:  # 遞歸結(jié)束條件，low是不能大于high的
        return

    mid = alist[low]  # 基數(shù)：初始值為序列中的第一個數(shù)值
    while low != high:
        # 先移動high
        while low < high:
            if mid < alist[high]:  # 下標(biāo)high對應(yīng)的值大于mid，high就向右偏移1
                high -= 1
            else:
                # 否則，就把將high指向的數(shù)值放置到左側(cè)下標(biāo)為low對應(yīng)的空位
                alist[low] = alist[high]
                break  # 傳遞后high下標(biāo)偏移結(jié)束
        # 開始移動low
        while low < high:
            if mid >= alist[low]:  # 下標(biāo)low對應(yīng)的值小于mid，low就向左偏移1
                low += 1
            else:
                # 否則，就把將low指向的數(shù)值放置到左側(cè)下標(biāo)為high對應(yīng)的空位
                alist[high] = alist[low]
                break  # 并結(jié)束

    # 最后當(dāng)low和high相等的時候，那么就把mid傳給下標(biāo)為low或high的位置
    if low == high:
        alist[low] = mid

    # 上述為核心操作，需要將核心操作遞歸作用到左右子序列中
    quick_sort(alist, left, low - 1)  # 遞歸到左側(cè)序列中
    quick_sort(alist, high + 1, right)  # 遞歸到右側(cè)序列中

    return alist


alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
print(quick_sort(alist, 0, len(alist) - 1))

# 輸出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]