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