python如何實(shí)現(xiàn)常用的五種排序算法詳解
發(fā)布日期：2022-02-15 08:14 | 文章來(lái)源：站長(zhǎng)之家
一、冒泡排序
原理：
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大就交換他們兩個(gè)
- 每一對(duì)相鄰元素做同樣的工作，直到結(jié)尾最后一對(duì)
- 每個(gè)元素都重復(fù)以上步驟，除了最后一個(gè)
第一步：
將亂序中的最大值找出，逐一移到序列最后的位置
alist = [3, 5, 9, 2, 1, 7, 8, 6, 4] def bubble_sort(alist): # 找最大值的方式是通過(guò)對(duì)列表中的元素進(jìn)行兩兩比較，值大的元素逐步向后移動(dòng) # 序列中有n個(gè)元素，兩兩比較的話，需要比較n-1次 for i in range(len(alist) - 1): # 循環(huán)n-1次，控制兩兩比較的次數(shù) if alist[i] > alist[i + 1]: # 如果前面的元素大于后面的元素，交換兩個(gè)元素的位置，否則不做任何操作 alist[i], alist[i + 1] = alist[i + 1], alist[i] return alist print(bubble_sort(alist)) # 輸出：最大值已經(jīng)移動(dòng)到最右邊了 [3, 5, 2, 1, 6, 7, 8, 4, 9]
當(dāng)上述代碼已經(jīng)可以將序列中的最大值放置到合適的位置，然后我們就可以將上述操作繼續(xù)作用到 n-1 和元素對(duì)應(yīng)的新序列，則就可以將 n-1 個(gè)元素對(duì)應(yīng)的最大值放置到了 n-1 和元素的最后位置。
結(jié)論：發(fā)現(xiàn)如果將上述的操作逐步的作用 n-1 此就可以將整個(gè)序列變成有序的。
第二步：
將第一步的操作繼續(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]: # 如果前面的元素大于后面的元素，交換兩個(gè)元素的位置，否則不做任何操作 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ù)找最大（?。┑脑?，放到序列中上一個(gè)最大值的前一個(gè)位置
- 重復(fù)第二步，直到所有元素排序完畢
第一步：
將亂序中的元素兩兩比較，找出最大值，然后直接將最大值放置到序列最后的位置（將最大值直接和最后一個(gè)元素交換位置）
def select_sort(alist): max_index = 0 # 最大值元素的下標(biāo)，一開始假設(shè)下標(biāo)為0的元素為最大值 for i in range(len(alist) - 1): # 循環(huán)控制兩兩比較的次數(shù) # 如果在比較的過(guò)程中發(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ù)和最后一個(gè)值做交換 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ù) # 如果在比較的過(guò)程中發(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ù)和最后一個(gè)值做交換 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))
三、插入排序
思路：
- 需要將原始序列分為兩個(gè)部分：有序部分、無(wú)序部分。
- 將無(wú)序部分中的元素逐一插入到有序部分中
注意：初始情況下，有序部分為亂序序列中的第一個(gè)元素，無(wú)序部分為亂序序列的 n-1 個(gè)元素
例如：
# 亂序序列：[8,3,5,7,6] [8, 3,5,7,6] # 8就是初始的有序部分，3、5、7、6就是初始的無(wú)序部分 [3,8, 5,7,6] [3,5,8, 7,6] [3,5,7,8, 6] [3,5,7,6,8,]
第一步：
定義一個(gè)變量 i ，i 表示的是有序部分元素的個(gè)數(shù)和無(wú)序部分第一個(gè)元素小標(biāo)
alist = [8, 3, 1, 6, 7] i = 1 # i 就是有序部分元素的個(gè)數(shù)和無(wú)序部分第一個(gè)元素下標(biāo) # alist[i-1]：有序部分最后一個(gè)元素下標(biāo) # alist[i]：無(wú)序部分第一個(gè)元素下標(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)作用到每個(gè)元素中
alist = [8, 3, 1, 6, 7] i = 2 # alist[i-1]：有序部分最后一個(gè)元素下標(biāo) # alist[i]：無(wú)序部分第一個(gè)元素下標(biāo) while i > 0: if alist[i - 1] > alist[i]: # 循環(huán)第一次時(shí)[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]：有序部分最后一個(gè)元素下標(biāo) # alist[i]：無(wú)序部分第一個(gè)元素下標(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 # 初識(shí)增量 # 將插入排序中的增量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 # 初識(shí)增量 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
五、快速排序
思路：
- 將列表中第一個(gè)元素設(shè)定為基準(zhǔn)數(shù)字，賦值給mid變量，然后將整個(gè)列表中比基準(zhǔn)小的數(shù)值放在基準(zhǔn)的左側(cè)，比基準(zhǔn)大的數(shù)字放在基準(zhǔn)右側(cè)，然后將基準(zhǔn)數(shù)字左右兩側(cè)的序列在根據(jù)此方法進(jìn)行排放
- 定義兩個(gè)指針，low 指向最左側(cè)，high 指向最右側(cè)
- 然后對(duì)最右側(cè)指針進(jìn)行向左移動(dòng)，移動(dòng)法則是，如果指針指向的數(shù)值比基準(zhǔn)小，則將指針指向的數(shù)字移動(dòng)到基準(zhǔn)數(shù)字原始位置，否則繼續(xù)移動(dòng)指針。
- 如果最右側(cè)指針指向的數(shù)值移動(dòng)到基準(zhǔn)位置時(shí)，開始移動(dòng)最左側(cè)指針，將其向右移動(dòng)，如果該指針指向的數(shù)值大于基準(zhǔn)側(cè)將該數(shù)值移動(dòng)到最右側(cè)指針指向的位置，然后停止移動(dòng)。
- 如果左右側(cè)指針重復(fù)則，將基準(zhǔn)放入左右指針重復(fù)的位置，則基準(zhǔn)左側(cè)為比其小的數(shù)值，右側(cè)為比其大的數(shù)值
第一步：
核心操作，將基數(shù) mid 放置到序列中間，使得基數(shù)左側(cè)都是比它小的，右側(cè)是比它大的
def quick_sort(alist): low = 0 # 第一個(gè)元素下標(biāo) high = len(alist) - 1 # 最后一個(gè)元素下標(biāo) mid = alist[low] # 基數(shù)：初始值為序列中的第一個(gè)數(shù)值 while low != high: # 先移動(dòng)high while low < high: if mid < alist[high]: # 下標(biāo)high對(duì)應(yīng)的值大于mid，high就向右偏移1 high = high - 1 else: # 否則，就把將high指向的數(shù)值放置到左側(cè)下標(biāo)為low對(duì)應(yīng)的空位 alist[low] = alist[high] break # 傳遞后high下標(biāo)偏移結(jié)束 # 開始移動(dòng)low while low < high: if mid > alist[low]: # 下標(biāo)low對(duì)應(yīng)的值小于mid，low就向左偏移1 low = low + 1 else: # 否則，就把將low指向的數(shù)值放置到左側(cè)下標(biāo)為high對(duì)應(yīng)的空位 alist[high] = alist[low] break # 并結(jié)束 # 最后當(dāng)low和high相等的時(shí)候，那么就把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ù)拆分出的左右子序列呢？可以通過(guò)傳入指定的left和right來(lái)指定不同的子序列 def quick_sort(alist, left, right): low = left # 第一個(gè)元素下標(biāo) high = right # 最后一個(gè)元素下標(biāo) if low > high: # 遞歸結(jié)束條件，low是不能大于high的 return mid = alist[low] # 基數(shù)：初始值為序列中的第一個(gè)數(shù)值 while low != high: # 先移動(dòng)high while low < high: if mid < alist[high]: # 下標(biāo)high對(duì)應(yīng)的值大于mid，high就向右偏移1 high -= 1 else: # 否則，就把將high指向的數(shù)值放置到左側(cè)下標(biāo)為low對(duì)應(yīng)的空位 alist[low] = alist[high] break # 傳遞后high下標(biāo)偏移結(jié)束 # 開始移動(dòng)low while low < high: if mid >= alist[low]: # 下標(biāo)low對(duì)應(yīng)的值小于mid，low就向左偏移1 low += 1 else: # 否則，就把將low指向的數(shù)值放置到左側(cè)下標(biāo)為high對(duì)應(yīng)的空位 alist[high] = alist[low] break # 并結(jié)束 # 最后當(dāng)low和high相等的時(shí)候，那么就把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]
總結(jié)
到此這篇關(guān)于python如何實(shí)現(xiàn)常用的五種排序算法的文章就介紹到這了,更多相關(guān)python實(shí)現(xiàn)排序算法內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
相關(guān)文章
關(guān)注官方微信