python排序算法的簡單實現方法

更新時間：2021年05月10日 09:21:03 作者：KKang@

這篇文章主要給大家介紹了關于python排序算法的簡單實現方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

1 冒泡排序

1.1 算法步驟：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

針對所有的元素重復以上的步驟，除了最后一個。

持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

（1）不管原始數組是否有序，時間復雜度都是O（n2）

（2）空間復雜度是O（1）

（3）冒泡排序是從最后一位開始確定最大或最小的數，保證后面的數都是有序的且都大于或小于前面的數

1.2 算法實現

def bubble_sort(alist):
    for i in range(len(alist) - 1):
        for j in range(len(alist) - 1 - i):##最后的幾位已經確定好大小的不用再次參與排序
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                count += 1
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)

1.3 算法優(yōu)化

def bubble_sort(alist):
    for i in range(len(alist) - 1):
        count = 0  ## 記錄交換的次數
        for j in range(len(alist) - 1 - i):
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                count += 1 ## 如果此次遍歷為未發(fā)生交換，則說明數據是有序的
        if count == 0:
            return
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)

2 選擇排序

2.1 算法步驟

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

2.2 算法實現

def select_sort(alist):
    for i in range(len(alist) - 1):
        min = i  ## i之前的元素已經確定位置，假設第i個元素為最小值
        for j in range(i, len(alist)):
            if alist[min] > alist[j]: ## 如果后面的元素比第i個元素小，則記錄該元素的索引為最小元素的索引
                min = j
            alist[i], alist[min] = alist[min], alist[i]
list = [3, 4, 2, 7, 11, 15, 5]
select_sort(list)
print(list)

3 插入排序

3.1 算法步驟

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。

3.2 算法實現

def insert_sort(alist):
    for i in range(1, len(alist)):
        for j in range(i, 0, -1):  ## 倒序取從下標i的元素開始到下標0
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]


list = [3, 4, 2, 7, 11, 15, 5]
insert_sort(list)
print(list)

3.3 算法優(yōu)化

def insert_sort(alist):
    for i in range(1, len(alist)):
        for j in range(i, 0, -1):  ## 倒序取從下標i的元素開始到下標0
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]
            else: ## 如果當前數值大于前一個數值，退出
                break


list = [3, 4, 2, 7, 11, 15, 5]
insert_sort(list)
print(list)

4 快速排序

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。

4.1 算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

從數列中挑出一個元素，稱為 “基準”（pivot）；
將大于pivot的值放在pivot的右邊；
將小于pivot的值放在pivot的左邊；
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序

4.2 算法實現

def quickSort(left, right, lst):
    l, r = left, right ## 確定左右指針
    if left >= right: ## 如果序列只有一個元素，則退出排序
        return
    ## 確定基準數為最左側元素
    base = lst[left]
    ## base為序列最左側元素，則應為右指針先左移，然后左指針右移  
    while l < r:
        while l < r and lst[r] >= base: ## 如果l<r同時最右側的值大于等于base，則向左移動r指針，退出的條件右指針的值<base
            r -= 1
        while l < r and lst[l] <= base: ## 如果l<r同時最左側的值小于等于base，則向右移動l指針,退出的條件左指針的值>base
            l += 1
        if l < r:  ##  如果左指針小于右指針（同時lst[r] < base lst[l] > base，滿足上述兩個條件）,則交換左右指針的值
            lst[l], lst[r] = lst[r], lst[l] 
    lst[l], lst[left] = lst[left], lst[l] ## 基準數回歸，將左右指針所指元素和基準數進行交換
    ## 此時一次排序結束
    
    quickSort(left, l - 1, lst) ## 對基準數左側序列進行排序
    quickSort(l + 1, right, lst)  ## 對基準數右側序列進行排序
list = [3, 4, 2, 7, 11, 15, 5]
end = len(list) - 1
quickSort(0, end, list)  ## 開始位置索引，結束位置索引，列表
print(list)

4 四種排序算法的比較

算法	時間復雜度（平均）	空間復雜度	穩(wěn)定性
冒泡排序	O(n²)	O(1)	穩(wěn)定
選擇排序	O(n²)	O(1)	不穩(wěn)定
插入排序	O(n²)	O(1)	穩(wěn)定
快速排序	O(nlog₂n)	O(nlog₂n)	不穩(wěn)定