无码不卡的中文字幕视频,最近中文字幕国语免费完整

主頁 > 知識庫 > python排序算法的簡單實現(xiàn)方法

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

1 冒泡排序

1.1 算法步驟：

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

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

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

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

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

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

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

1.2 算法實現(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ā)生交換，則說明數(shù)據(jù)是有序的
        if count == 0:
            return
list = [3, 4, 2, 7, 11, 15, 5]
bubble_sort(list)
print(list)

2 選擇排序

2.1 算法步驟

在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。
再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢

2.2 算法實現(xiàn)

def select_sort(alist):
    for i in range(len(alist) - 1):
        min = i  ## i之前的元素已經(jīng)確定位置，假設(shè)第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 算法步驟

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

3.2 算法實現(xiàn)

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


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

4 快速排序

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

4.1 算法描述

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

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

4.2 算法實現(xiàn)

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

4 四種排序算法的比較

算法	時間復(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)定

總結(jié)

到此這篇關(guān)于python排序算法簡單實現(xiàn)的文章就介紹到這了,更多相關(guān)python排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

Python猜數(shù)字算法題詳解
python算法題鏈表反轉(zhuǎn)詳解
一道python走迷宮算法題
python實現(xiàn)dbscan算法
Python機器學(xué)習(xí)之PCA降維算法詳解
Python機器學(xué)習(xí)算法之決策樹算法的實現(xiàn)與優(yōu)缺點
Python實現(xiàn)K-means聚類算法并可視化生成動圖步驟詳解
用Python給圖像算法做個簡單應(yīng)用界面
python利用K-Means算法實現(xiàn)對數(shù)據(jù)的聚類案例詳解
python入門之算法學(xué)習(xí)
python實現(xiàn)線性回歸算法
Python實現(xiàn)七大查找算法的示例代碼
python 算法題——快樂數(shù)的多種解法

標(biāo)簽：益陽黑龍江上海常德黔西鷹潭惠州四川

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《python排序算法的簡單實現(xiàn)方法》，本文關(guān)鍵詞 python,排序,算法,的,簡單,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。