目錄
- 一、冒泡排序
- 二、選擇排序
- 三、插入排序
- 四、希爾排序
- 五、快速排序
- 總結
一、冒泡排序
原理：
- 比較相鄰的元素。如果第一個比第二個大就交換他們兩個
- 每一對相鄰元素做同樣的工作，直到結尾最后一對
- 每個元素都重復以上步驟，除了最后一個
第一步：
將亂序中的最大值找出，逐一移到序列最后的位置
alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
def bubble_sort(alist):
# 找最大值的方式是通過對列表中的元素進行兩兩比較，值大的元素逐步向后移動
# 序列中有n個元素，兩兩比較的話，需要比較n-1次
for i in range(len(alist) - 1): # 循環n-1次，控制兩兩比較的次數
if alist[i] > alist[i + 1]:
# 如果前面的元素大于后面的元素，交換兩個元素的位置，否則不做任何操作
alist[i], alist[i + 1] = alist[i + 1], alist[i]
return alist
print(bubble_sort(alist))
# 輸出：最大值已經移動到最右邊了
[3, 5, 2, 1, 6, 7, 8, 4, 9]
當上述代碼已經可以將序列中的最大值放置到合適的位置，然后我們就可以將上述操作繼續作用到 n-1 和元素對應的新序列，則就可以將 n-1 個元素對應的最大值放置到了 n-1 和元素的最后位置。
結論：發現如果將上述的操作逐步的作用 n-1 此就可以將整個序列變成有序的。
第二步：
將第一步的操作繼續作用 n-1 次
alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
def bubble_sort(alist):
for j in range(len(alist)-1): # 外層循環次數遞增，內層循環次數遞減
for i in range(len(alist) - 1-j): # 循環次數需要遞減-j，控制兩兩比較的次數
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]
二、選擇排序
思路：
- 首先在序列中找到最大（小）元素，存放到序列的最后
- 在從剩余的序列元素中繼續找最大（小）的元素，放到序列中上一個最大值的前一個位置
- 重復第二步，直到所有元素排序完畢
第一步：
將亂序中的元素兩兩比較，找出最大值，然后直接將最大值放置到序列最后的位置（將最大值直接和最后一個元素交換位置）
def select_sort(alist):
max_index = 0 # 最大值元素的下標，一開始假設下標為0的元素為最大值
for i in range(len(alist) - 1): # 循環控制兩兩比較的次數
# 如果在比較的過程中發現，下標為max_index不是最大值，那么就改變max_index
if alist[max_index] alist[i + 1]:
max_index = i + 1
# 循環結束后max_index就一定是最大值的下標，并且把該數和最后一個值做交換
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]
第二步：
將第一步繼續作用 n-1 次
def select_sort(alist):
for j in range(len(alist) - 1):# 外層循環遞增n-1次
max_index = 0 # 最大值元素的下標，一開始假設下標為0的元素為最大值
for i in range(len(alist) - 1 - j): # 內層循環遞減，循環控制兩兩比較的次數
# 如果在比較的過程中發現，下標為max_index不是最大值，那么就改變max_index
if alist[max_index] alist[i + 1]:
max_index = i + 1
# 循環結束后max_index就一定是最大值的下標，并且把該數和最后一個值做交換
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 表示的是有序部分元素的個數和無序部分第一個元素小標
alist = [8, 3, 1, 6, 7]
i = 1 # i 就是有序部分元素的個數和無序部分第一個元素下標
# alist[i-1]：有序部分最后一個元素下標
# alist[i]：無序部分第一個元素下標
if alist[i - 1] > alist[i]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
# [3, 8, 1, 6, 7]
第二步：循環作用到每個元素中
alist = [8, 3, 1, 6, 7]
i = 2
# alist[i-1]：有序部分最后一個元素下標
# alist[i]：無序部分第一個元素下標
while i > 0:
if alist[i - 1] > alist[i]:
# 循環第一次時[3,1,8, 6,7]
alist[i], alist[i - 1] = alist[i - 1], alist[i]
i -= 1
# 循環繼續
# [1,3,8, 6，7]
else:
break
第三步：
處理變量 i，需要讓 i 進行自己遞增
for i in range(1, len(alist)): # i = [1,2,3,4]
# alist[i-1]：有序部分最后一個元素下標
# alist[i]：無序部分第一個元素下標
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
四、希爾排序
關鍵變量：增量gap
gap：初始值為 len(alist) // 2
插入排序就是增量為 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
第三步：
在第二步中進行增量的縮減（增量縮減到1結束）完整代碼
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
五、快速排序
思路：
- 將列表中第一個元素設定為基準數字，賦值給mid變量，然后將整個列表中比基準小的數值放在基準的左側，比基準大的數字放在基準右側，然后將基準數字左右兩側的序列在根據此方法進行排放
- 定義兩個指針，low 指向最左側，high 指向最右側
- 然后對最右側指針進行向左移動，移動法則是，如果指針指向的數值比基準小，則將指針指向的數字移動到基準數字原始位置，否則繼續移動指針。
- 如果最右側指針指向的數值移動到基準位置時，開始移動最左側指針，將其向右移動，如果該指針指向的數值大于基準側將該數值移動到最右側指針指向的位置，然后停止移動。
- 如果左右側指針重復則，將基準放入左右指針重復的位置，則基準左側為比其小的數值，右側為比其大的數值
第一步：
核心操作，將基數 mid 放置到序列中間，使得基數左側都是比它小的，右側是比它大的
def quick_sort(alist):
low = 0 # 第一個元素下標
high = len(alist) - 1 # 最后一個元素下標
mid = alist[low] # 基數：初始值為序列中的第一個數值
while low != high:
# 先移動high
while low high:
if mid alist[high]: # 下標high對應的值大于mid，high就向右偏移1
high = high - 1
else:
# 否則，就把將high指向的數值放置到左側下標為low對應的空位
alist[low] = alist[high]
break # 傳遞后high下標偏移結束
# 開始移動low
while low high:
if mid > alist[low]: # 下標low對應的值小于mid，low就向左偏移1
low = low + 1
else:
# 否則，就把將low指向的數值放置到左側下標為high對應的空位
alist[high] = alist[low]
break # 并結束
# 最后當low和high相等的時候，那么就把mid傳給下標為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]
第二步：
將第一步的核心操作遞歸作用到基數的左右兩側的子序列中
# 那么如何區分根據基數拆分出的左右子序列呢？可以通過傳入指定的left和right來指定不同的子序列
def quick_sort(alist, left, right):
low = left # 第一個元素下標
high = right # 最后一個元素下標
if low > high: # 遞歸結束條件，low是不能大于high的
return
mid = alist[low] # 基數：初始值為序列中的第一個數值
while low != high:
# 先移動high
while low high:
if mid alist[high]: # 下標high對應的值大于mid，high就向右偏移1
high -= 1
else:
# 否則，就把將high指向的數值放置到左側下標為low對應的空位
alist[low] = alist[high]
break # 傳遞后high下標偏移結束
# 開始移動low
while low high:
if mid >= alist[low]: # 下標low對應的值小于mid，low就向左偏移1
low += 1
else:
# 否則，就把將low指向的數值放置到左側下標為high對應的空位
alist[high] = alist[low]
break # 并結束
# 最后當low和high相等的時候，那么就把mid傳給下標為low或high的位置
if low == high:
alist[low] = mid
# 上述為核心操作，需要將核心操作遞歸作用到左右子序列中
quick_sort(alist, left, low - 1) # 遞歸到左側序列中
quick_sort(alist, high + 1, right) # 遞歸到右側序列中
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]
總結
到此這篇關于python如何實現常用的五種排序算法的文章就介紹到這了,更多相關python實現排序算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- 如何利用Python動態展示排序算法
- Python 列表排序詳解
- python編程冒泡排序法實現動圖排序示例解析
- python教程對函數中的參數進行排序
- python數據結構的排序算法
- Python實現堆排序案例詳解
- Python 數據結構之十大經典排序算法一文通關
