網站首頁 編程語言 正文
1. 前言
所謂排序，就是把一個數據群體按個體數據的特征按從大到小或從小到大的順序存放。
排序在應用開發中很常見，如對商品按價格、人氣、購買數量……顯示。
初學編程者，剛開始接觸的第一個稍微有點難理解的算法應該是排序算法中的冒泡算法。
我初學時，“腦思維”差點繞在 2 個循環結構的世界里出不來了。當時，老師要求我們死記冒泡的口訣，雖然有點搞笑，但是當時的知識層次只有那么點，口訣也許是最好的一種學習方式。
當知識體系慢慢建全，對于冒泡排序的理解，自然也會從形式到本質的理解。
本文先從冒泡排序的本質說起，不僅是形式上理解，而是要做到本質里的理解。
2. 冒泡排序算法
所謂冒泡排序算法，本質就是求最大值、最小值算法。
所以，可以暫時拋開冒泡排序，先從最大值算法聊起。
為了更好理解算法本質，在編寫算法時不建議直接使用 Python 中已經內置的函數。如 max()、min()……
求最大值，有多種思路，其中最常用的思路有：
擺擂臺法 相鄰的兩個數字比較法
如一個數列 nums=[3,1,8,9,12,32,7]
2.1 擺擂臺法
算法思想：
找一個擂臺，從數列中隨機拎一個數字出來，站在擂臺上充當老大。
老大不是說你想當就能當，要看其它的兄弟服不服。于是，其它的數字兄弟會一一登上擂臺和擂臺上的數字比較，原則是大的留下，小的離開。
如果是找最大值，則是大的留下，小的離開。
反之，如果是找最小值，則是小的留下，大的離開。
你方唱罷我登場。最后留在擂臺上的就是真老大了。
nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數字登上擂臺
m = nums[0]
# 其它數字不服氣
for i in range(1, len(nums)):
# PK 過程中，大的留在擂臺上
if nums[i] > m:
m = nums[i]
# 最后留在擂臺上的就是最大值
print("最大值是:", m)很簡單，對不對，如果，找到一個最大值后，再在余下的數字中又找最大值，以此類推，結局會怎樣？
最后可以讓所有數字都排好序！這就是排序的最本質道理，找著找著就排好序了。
在上面的代碼上稍做改動一下，每次找到最大值后存入到另一個列表中。
nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數字登上擂臺
ms=[]
for _ in range(len(nums)):
m = nums[0]
for i in range(1, len(nums)):
if nums[i] > m:
m = nums[i]
# 依次找到的最大值存入新數列
ms.append(m)
# 從原數列中移出找到的最大值，下一輪要在沒有它的數列中重新找，不移走，無論找多少次，還會是它
nums.remove(m)
print(ms)
'''
輸出結果
[32, 12, 9, 8, 7, 3, 1]
'''我們可以看到原數列中的數字全部都排序了。但是上述排序算法不完美：
另開辟了新空間，顯然空間復雜度增加了。 原數列的最大值找到后就刪除了，目的是不干擾余下數字繼續查找最大值。當對所有數字排好序后，原數列也破壞了。
能不能不開辟新空間，在原數列里就完成排序？當然可以。
可以找到最大值就向后移！原數列從邏輯上從右向左縮小。
nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數字登上擂臺
nums_len = len(nums)
for _ in range(len(nums)):
m = nums[0]
for i in range(1, nums_len):
if nums[i] > m:
m = nums[i]
# 最大值找到，移動最后
nums.remove(m)
nums.append(m)
# 這個很關鍵，縮小原數列的結束位置
nums_len = nums_len - 1
print(nums)
'''
輸出結果:
[32, 12, 9, 8, 7, 3, 1]
'''在原數列上面，上述代碼同樣完成了排序。
歸根結底，上述排序的思路就是不停地找最大值呀、找最大值……找到最后一個數字，大家自然而然就排好序了。
所以算法結構中內層循環是核心找最大值邏輯，而外層就是控制找呀找呀找多少次。
上述排序算法我們也可稱是冒泡排序算法，其時間復雜度=外層循環次數X內層循環次數。如有 n 個數字 ，則外層循環 n-1 次，內層循環 n-1 次，在大 O 表示法中，常量可以忽視不計，時間復雜度應該是 O（n<sup>2</sup>）。
2.2 相鄰兩個數字相比較
如果有 7 個數字，要找到里面的最大值，有一種方案就是每相鄰的兩個數字之行比較，如果前面的比后面的數字大，則交換位置，否則位置不動。 上體育課的時候，老師排隊用的就是這種方式，高的和矮的交換位置，一直到不能交換為此。
nums = [3, 1, 8, 9, 12, 32, 7]
for i in range(len(nums)-1):
# 相鄰 2 個數字比較
if nums[i] > nums[i + 1]:
# 如果前面的數字大于后面的數字，則交換
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# 顯然，數列最后位置的數字是最大的
print(nums[len(nums) - 1])
'''
輸出結果
32
'''上述代碼同樣實現了找最大值。
和前面的思路一樣，如果找了第一個最大值后，又繼續在剩下的數字中找最大值，不停地找呀找，會發現最后所有數字都排好序了。
在上述找最大值的邏輯基礎之上，再在外面嵌套一個重復語法，讓找最大值邏輯找完一輪又一輪，外層重復只要不少于數列中數字長度，就能完成排序工作，即使外層重復大于數列中數字長度，只是多做了些無用功而已。
nums = [3, 1, 8, 9, 12, 32, 7]
# 外層重復的 100 意味著找了 100 次最大值，這里只是說明問題，就是不停找最大值，顯然，是用不著找100 次的
for j in range(100):
for i in range(len(nums)-1):
# 相鄰 2 個數字比較
if nums[i] > nums[i + 1]:
# 如果前面的數字大于后面的數字，則交換
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)上面的代碼就是冒泡排序算法實現。其實冒泡排序就是找了一輪最大值，又繼續找最大值的思路。可以對上述算法進行一些優化，如已經找到的最大值沒有必要再參與后繼的找最大值中去。
顯然，找最大值的最多輪數是數列長度減 1 就可以了。5 個數字，前面 4 個找到了，自然大家就都排好序了。
nums = [3, 1, 8, 9, 12, 32, 7]
# 找多少次最大值，數列長度減 1
for j in range(len(nums)-1):
for i in range(len(nums)-1-j):
# 相鄰 2 個數字比較
if nums[i] > nums[i + 1]:
# 如果前面的數字大于后面的數字，則交換
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)在學習冒泡排序算法時，不要被外層、內層循環結構嚇住，核心是理解求最大值算法。上述冒泡排序算法的時間復雜度也是 O（n<sup>2</sup>）。
3. 選擇排序算法
**選擇排序算法是冒泡排序的變種，還是在找最大（小）值算法，**冒泡排序是一路比較一路交換，為什么要這樣，因為不知道數列中哪一個數字是最大（小）值，所以只能不停的比較不停的交換。
選擇排序有一個優于冒泡的理念，需要交換時才交換。
所以選擇排序算法的問題就是什么時候需要交換？
選擇排序先是假設第一個數字是最小值，然后在后面的數字里找有沒有比這個假設更小的。不是說，找一個小的就交換，因為有可能還有比之更小的，只有當后續所有數字找完后，再確定進行交換，
還是使用擂擂臺算法實現找最大（小）值，找到后交換位置。
nums = [6, 2, 5, 9, 12, 1, 7]
# 擂臺！假充第一 個數字是最小值
mi = nums[0]
# 假設的最小數字位置
mi_idx = 0
# 真正最小數字的位置
real_idx = mi_idx
for i in range(mi_idx + 1, len(nums)):
if nums[i] < mi:
mi = nums[i]
# 記住更小數字的位置，不記著交換
real_idx = i
# 如有更小的
if real_idx != mi_idx:
# 交換
nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
輸出結果
[1, 2, 5, 9, 12, 6, 7]
'''以上代碼就是選擇排序的核心邏輯，實現了把最小的數字移動最前面。
再在上述邏輯基礎上，繼續在后續數字中找出最小值，并移動前面。多找幾次就可以了！本質和冒泡算法還是一樣的，不停找最大（小）值。
nums = [6, 2, 5, 9, 12, 1, 7]
for j in range(len(nums)-1):
mi = nums[j]
# 假設的最小數字位置
mi_idx = j
# 真正最小數字的位置
real_idx = mi_idx
for i in range(mi_idx + 1, len(nums)):
if nums[i] < mi:
mi = nums[i]
# 記住更小數字的位置
real_idx = i
# 如有更小的
if real_idx != mi_idx:
# 交換
nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
輸出結果:
[1, 2, 5, 6, 7, 9, 12]
'''選擇排序的時間復雜度和冒泡排序的一樣 O（n<sup>2</sup>）。
4. 插入排序
打牌的時候，我們剛拿到手上的牌是無序的，在整理紙牌并讓紙牌一步一步變得的有序的過程就是插入算法的思路。
插入排序的核心思想：
把原數列從邏輯(根據起始位置和結束位置在原數列上劃分)上分成前、后兩個數列，前面的數列是有序的，后面的數列是無序的。
剛開始時，前面的數列（后面簡稱前數列）只有唯一的一個數字，即原數列的第一個數字。顯然是排序的！
依次從后數列中逐個拿出數字，與前數列的數字進行比較，保證插入到前數列后，整個前數列還是有序的。
如上，從后數列中拿到數字 1 ，然后與前數字的 3 進行比較，如果是從大到小排序，則 1 就直接排到 3 后面，如果是從小到大排序，則 1 排到 3 前面。
這里，按從小到大排序。
從如上描述可知，插入排序核心邏輯是：
比較： 后數列的數字要與前數字的數字進行大小比較，這個與冒泡和選擇排序沒什么不一樣。 移位： 如果前數列的數字大于后數列的數字，則需要向后移位。也可以和冒泡排序一樣交換。 插入： 為后數列的數字在前數列中找到適當位置后，插入此數據。
插入排序的代碼實現：
這里使用前指針和后指針的方案。
前指針用來在前數列中定位數字，方向是從右向左。
后指針用來在后數字中定位數字，方向是從左向右。
前指針初始的位置之前為前數列，后指針初始時的位置為后數列。
nums = [3, 1, 8, 9, 12, 32, 7]
# 后指針指向原數列的第 2 個數字,所以索引號從 1 開始
for back_idx in range(1, len(nums)):
# 前指針和后指針的關系，
front_idx = back_idx - 1
# 臨時變量，比較時，前數列的數字有可能要向后移位，需要把后指針指向的數字提前保存
tmp = nums[back_idx]
# 與前數列中的數字比較
while front_idx >= 0 and tmp < nums[front_idx]:
# 移位
nums[front_idx + 1] = nums[front_idx]
front_idx -= 1
if front_idx != back_idx - 1:
# 插入
nums[front_idx + 1] = tmp
print(nums)
'''
輸出結果
[1,3,7,8,9,12,32]
'''上述代碼用到了移位和插入操作，也可以使用交換操作。如果是交換操作，則初始時，前、后指針可以指向同一個位置。
nums = [3, 1, 8, 9, 12, 32, 7]
for back_idx in range(1, len(nums)):
for front_idx in range(back_idx, 0, -1):
if nums[front_idx] < nums[front_idx - 1]:
nums[front_idx], nums[front_idx - 1] = nums[front_idx - 1], nums[front_idx]
else:
break
print(nums)后指針用來選擇后數列中的數字，前指針用來對前數列相鄰數字進行比較、交換。和冒泡排序一樣。
這里有一個比冒泡排序優化的地方，冒泡排序需要對數列中所有相鄰兩個數字進行比較，不考慮是不是有必要比較。
但插入不一樣，因插入是假設前面的數列是有序的，所以如果后指針指向的數字比前數列的最后一個數字都大，顯然，是不需要再比較下去，如下的數字 `` 是不需要和前面的數字進行比較，直接放到前數列的尾部。
插入排序的時間復雜度還是 O(n<sup>2</sup>) 。
5. 快速排序
快速排序是一個很有意思的排序算法，快速排序的核心思想：
分治思想： 全局到局部、或說是粗糙到完美的逐步細化過程。
類似于畫人物畫。
先繪制一個輪廓圖，讓其看起來像什么！
然后逐步細化，讓它真的就是什么！
快速排序也是這個思想，剛開始，讓數列粗看起來有序，通過逐步迭代，讓其真正有序。
二分思想： 在數列選擇一個數字（基數）為參考中心，數列比基數大的，放在左邊（右邊），比基數小的，放在右邊（左邊）。
第一次的二分后：整個數列在基數之上有了有序的輪廓，然后在對基數前部分和后部分的數字繼續完成二分操作。
這里使用左、右指針方式描述快速排序：
左指針初始指向最左邊數字。 右指針初始指向最右邊數字。
這里選擇 8 作為第一次二分的基數，基數的選擇沒有特定要求，只要是數列中的數字，別客氣，任意選擇。這里把比 8 小的移到 8 的左邊，比 8 大的移動 8 的右邊。
移位的流程：
左指針不停向右移動，至到遇到大于等于基數的數字 ，同理右指針不停向左移動，至到碰到小于等于基數的數字。 交換左指針和右指針的位置的數據。
如上圖，左指針最后會停止在數字 8 所在位置，右指針會停在數字 7 所在位置。
交換左、右指針位置的數字。
依此類推，繼續移動指針、交換。
第一次二分后，整個數列會變成如下圖所示：
當左、右指針重合在一起時，第一次二分過程到此結束。以基數 8 為分界線，把原數列分成前、后兩部分，繼續在前、后數列上面使用如上二分思想 。顯然，使用遞歸是最直接有效的選擇。
如下第一次二分代碼：
nums = [3, 1, 8, 32, 2, 9, 7]
def quick_sort(nums):
# 左指針
left = 0
# 右指針
right = len(nums) - 1
# 基數，可以是任意數字，一般選擇數列的第一個數字
base_n = 8
while left < right:
# 左指針向右移動，至到時左指針位置數字大于等于基數，
while nums[left] < base_n and left < right:
left += 1
while nums[right] > base_n and right > left:
right -= 1
# 交換
nums[left], nums[right] = nums[right], nums[left]
quick_sort(nums)
print(nums)輸出結果：
[3, 1, 7, 2, 8, 9, 32]
和上面的演示流程圖的結果一樣。
使用遞歸進行多次二分：
nums = [3, 1, 8, 32, 2, 9, 7]
def quick_sort(nums, start, end):
if start >= end:
return
# 左指針
left = start
# 右指針
right = end
# 基數
base_n = nums[start]
while left < right:
while nums[right] > base_n and right > left:
right -= 1
# 左指針向右移動，至到時左指針位置數字大于等于基數，
while nums[left] < base_n and left < right:
left += 1
# 交換
nums[left], nums[right] = nums[right], nums[left]
# 左邊數列
quick_sort(nums, start, left - 1)
# 右邊數列
quick_sort(nums, right + 1, end)
quick_sort(nums, 0, len(nums) - 1)
print(nums)
'''
輸出結果
[1, 2, 3, 7, 8, 9, 32]
'''快速排序的時間復雜度為 O(nlogn)，空間復雜度為O(nlogn)。
6. 總結
除了冒泡、選擇、插入、快速排序算法，還有很多其它的排序算法，冒泡、選擇 、插入算法很類似，有其相似的比較、交換邏輯。快速排序使用了分治理念，可從減少時間復雜度。
原文鏈接：https://blog.51cto.com/gkcode/5195936
相關推薦
- 2022-06-29 C++詳細講解IO流原理_C 語言
- 2022-07-01 python性能檢測工具函數運行內存及運行時間_python
- 2022-10-14 【Python】pytorch 保存模型、checkpoint
- 2022-04-23 uniapp封裝本地存儲處理數據的方法和具體使用
- 2023-01-20 python如何求兩數之和及多數之和_python
- 2022-12-31 go操作Kafka使用示例詳解_Golang
- 2022-02-07 SSH連服務器提示“Permission denied，please try again”的原因與解
- 2022-07-02 Python遠程SSH庫Paramiko詳細操作_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速