快捷導(dǎo)航

python排序算法的簡(jiǎn)單實(shí)現(xiàn)方法

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

這篇文章主要給大家介紹了關(guān)于python排序算法的簡(jiǎn)單實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

1 冒泡排序

1.1 算法步驟：

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

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

（1）不管原始數(shù)組是否有序，時(shí)間復(fù)雜度都是O（n2）

（2）空間復(fù)雜度是O（1）

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

1.2 算法實(shí)現(xiàn)

def bubble_sort(alist):
    for i in range(len(alist) - 1):
        for j in range(len(alist) - 1 - i):##最后的幾位已經(jīng)確定好大小的不用再次參與排序
            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  ## 記錄交換的次數(shù)
        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ā)生交換，則說(shuō)明數(shù)據(jù)是有序的
        if count == 0:
            return
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)

2 選擇排序

2.1 算法步驟

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢

2.2 算法實(shí)現(xiàn)

def select_sort(alist):
    for i in range(len(alist) - 1):
        min = i  ## i之前的元素已經(jīng)確定位置，假設(shè)第i個(gè)元素為最小值
        for j in range(i, len(alist)):
            if alist[min] > alist[j]: ## 如果后面的元素比第i個(gè)元素小，則記錄該元素的索引為最小元素的索引
                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 算法步驟

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

3.2 算法實(shí)現(xiàn)

def insert_sort(alist):
    for i in range(1, len(alist)):
        for j in range(i, 0, -1):  ## 倒序取從下標(biāo)i的元素開(kāi)始到下標(biāo)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):  ## 倒序取從下標(biāo)i的元素開(kāi)始到下標(biāo)0
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]
            else: ## 如果當(dāng)前數(shù)值大于前一個(gè)數(shù)值，退出
                break


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

4 快速排序

快速排序的基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。

4.1 算法描述

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

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

4.2 算法實(shí)現(xiàn)

def quickSort(left, right, lst):
    l, r = left, right ## 確定左右指針
    if left >= right: ## 如果序列只有一個(gè)元素，則退出排序
        return
    ## 確定基準(zhǔn)數(shù)為最左側(cè)元素
    base = lst[left]
    ## base為序列最左側(cè)元素，則應(yīng)為右指針先左移，然后左指針右移  
    while l < r:
        while l < r and lst[r] >= base: ## 如果l<r同時(shí)最右側(cè)的值大于等于base，則向左移動(dòng)r指針，退出的條件右指針的值<base
            r -= 1
        while l < r and lst[l] <= base: ## 如果l<r同時(shí)最左側(cè)的值小于等于base，則向右移動(dòng)l指針,退出的條件左指針的值>base
            l += 1
        if l < r:  ##  如果左指針小于右指針（同時(shí)lst[r] < base lst[l] > base，滿足上述兩個(gè)條件）,則交換左右指針的值
            lst[l], lst[r] = lst[r], lst[l] 
    lst[l], lst[left] = lst[left], lst[l] ## 基準(zhǔn)數(shù)回歸，將左右指針?biāo)冈睾突鶞?zhǔn)數(shù)進(jìn)行交換
    ## 此時(shí)一次排序結(jié)束
    
    quickSort(left, l - 1, lst) ## 對(duì)基準(zhǔn)數(shù)左側(cè)序列進(jìn)行排序
    quickSort(l + 1, right, lst)  ## 對(duì)基準(zhǔn)數(shù)右側(cè)序列進(jìn)行排序
list = [3, 4, 2, 7, 11, 15, 5]
end = len(list) - 1
quickSort(0, end, list)  ## 開(kāi)始位置索引，結(jié)束位置索引，列表
print(list)

4 四種排序算法的比較

算法	時(shí)間復(fù)雜度（平均）	空間復(fù)雜度	穩(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)定