在計(jì)算機(jī)科學(xué)的世界中，排序算法無(wú)疑是最為經(jīng)典和基礎(chǔ)的主題之一。排序不僅是解決各種計(jì)算問(wèn)題的基礎(chǔ)，而且在日常編程中也是必不可少的一環(huán)。Python這一富有表達(dá)力的編程語(yǔ)言，提供了許多強(qiáng)大的工具和庫(kù)，使得實(shí)現(xiàn)和理解排序算法變得更加直觀和有趣。
本篇博客將帶領(lǐng)大家探索Python中一些常見(jiàn)的排序算法，從簡(jiǎn)單到復(fù)雜，深入剖析它們的工作原理、性能特點(diǎn)以及在實(shí)際應(yīng)用中的巧妙之處。無(wú)論你是初學(xué)者還是有一定經(jīng)驗(yàn)的開(kāi)發(fā)者，通過(guò)本文的學(xué)習(xí)，你將更好地理解排序算法的本質(zhì)，并能夠在實(shí)際項(xiàng)目中明智地選擇和應(yīng)用合適的算法。
讓我們開(kāi)始這次關(guān)于Python排序算法之旅吧！
一、排序算法種類(lèi)
在學(xué)習(xí)具體的排序算法之前，我們先簡(jiǎn)單了解一下，排序算法都有哪些吧！
我認(rèn)為排序算法可以大致分為以下幾類(lèi)：
?大致了解了排序算法有哪些后，我們來(lái)聊聊具體算法的實(shí)現(xiàn)過(guò)程以及排序的思想
二、簡(jiǎn)單排序算法
1.冒泡排序
- 算法實(shí)現(xiàn)過(guò)程
通過(guò)比較相鄰的元素，如果前一個(gè)比后一個(gè)大，就把它們兩個(gè)對(duì)調(diào)位置。
一趟排序完成后，則無(wú)序區(qū)減少一個(gè)數(shù)，有序區(qū)增加一個(gè)數(shù)。
對(duì)序列中的每一對(duì)相鄰元素做同樣的工作，直到序列全部完成。
冒泡循環(huán)需要遍歷n-1次（n為序列的長(zhǎng)度）?。
- 時(shí)間復(fù)雜度 o(n2)
- 代碼實(shí)現(xiàn)
def bubble_sort(li):
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return最外層循環(huán)指的是冒泡循環(huán)需要遍歷n-1次（n為列表長(zhǎng)度），內(nèi)層循環(huán)到n-i-1的原因是比如第一趟過(guò)后，頂端最大的數(shù)字已經(jīng)找出，并且這個(gè)最大的數(shù)已經(jīng)在有序區(qū)中了，只需要用同樣的方法遍歷剩下的無(wú)序區(qū)，找出無(wú)序區(qū)中最大的數(shù)即可。
這里也介紹了交換兩個(gè)數(shù)的方法,即? li[i], li[i+1] = li[i+1], li[i]?。
exchange是一個(gè)標(biāo)志位，他的作用是如果在某一趟排序中，沒(méi)有發(fā)生任何交換，此時(shí)可以說(shuō)明無(wú)序區(qū)本來(lái)就是已經(jīng)排列好的，不需要進(jìn)行后續(xù)的排序。這里每一趟之后都需要檢驗(yàn)，所以注意縮進(jìn)。
這里默認(rèn)是升序排列，若要改為降序排列，只需要將判斷語(yǔ)句中的‘>’改為‘<’即可。
2.選擇排序
- 算法實(shí)現(xiàn)過(guò)程
每一輪從待排序的記錄中選出最小的元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚≡?，然后放到已排序的序列的末尾?/p>
也可以每一輪找出數(shù)值最大的元素，這樣的話，排序完畢后的數(shù)組最終是從大到小排列。
選擇排序每次選出最?。ㄗ畲螅┑脑?，因此需要遍歷 n-1 次。
- 時(shí)間復(fù)雜度?o(n2)
注意：該選擇排序的時(shí)間復(fù)雜度是o(n2)，而不是o(n)，這是因?yàn)樵谘h(huán)體中內(nèi)置函數(shù)min()和remove()的復(fù)雜度都是o(n)，而不是o(1)，這兩個(gè)函數(shù)的本質(zhì)都是將整個(gè)序列遍歷一遍，從而找出最小值和要?jiǎng)h除的值
- 代碼實(shí)現(xiàn)
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new建立一個(gè)新的列表，遍歷原列表，用內(nèi)置函數(shù)min()找出列表中的最小值，把他存儲(chǔ)在變量min_val中，在新建列表中加入這個(gè)值，并且將這個(gè)值從原始列表中刪除，重復(fù)以上操作。?
- 代碼優(yōu)化
由于以上代碼需要再申請(qǐng)一塊新的內(nèi)存來(lái)存放排好序的列表，浪費(fèi)空間，所以我們想辦法對(duì)代碼進(jìn)行優(yōu)化，我們可以把選擇出來(lái)的最小的數(shù)與列表第一個(gè)位置的數(shù)進(jìn)行交換，后面我只需要找無(wú)序區(qū)數(shù)中的最小值與無(wú)序區(qū)的第一個(gè)數(shù)進(jìn)行比較交換，這樣就能實(shí)現(xiàn)原地排序，節(jié)省了大量?jī)?nèi)存。由于要交換位置，那么就要記錄下標(biāo)，由于上面說(shuō)到要與無(wú)序區(qū)的第一個(gè)數(shù)進(jìn)行交換，所以min_loc的下標(biāo)要記作i，后面只需要遍歷無(wú)序區(qū)即可，所以j的范圍是從i+1到n。
def select_sort(li):
for i in range(len(li)):
min_loc = i # 遍歷的是無(wú)序區(qū)的位置
for j in range(i + 1, len(li)): # 前包后不包，所以這里后面應(yīng)當(dāng)寫(xiě)列表長(zhǎng)度,從i+1開(kāi)始可以省去自己和自己比較的那一步
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
print(li)
3.插入排序?
- 算法實(shí)現(xiàn)過(guò)程
插入排序就是每一步都將一個(gè)需要排序的數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)序列中的適當(dāng)位置，直到全部插入完畢。插入排序就如同打撲克牌一樣，每次將后面抽到的牌按順序插到前面已經(jīng)排好序的牌中。
- 時(shí)間復(fù)雜度 o(n2)?
- 代碼實(shí)現(xiàn)
def insert_sort(li):
for i in range(1, len(li)): # 前包后不包
tmp = li[i]
j = i - 1 # j指的是手里的牌的下標(biāo)
while j >= 0 and li[j] > tmp:
li[j + 1] = li[j]
j = j - 1
li[j + 1] = tmp
最外層的循環(huán)i的范圍是從1到n(n為序列的長(zhǎng)度)，這是因?yàn)槲业哪康氖潜闅v所有牌和我手中的作比較，相當(dāng)于每次抽取一張牌，和我手中已有的牌數(shù)進(jìn)行比較，然后把它們插入在合適的位置中，我抽取的第一張牌下標(biāo)為0，所以我只需要從1開(kāi)始比較就可以，所以i的范圍從1開(kāi)始。?
j表示我手里被比較的那張牌，如果j這張牌，比我新抽到的牌數(shù)值大，那么就需要j這張牌往右挪一個(gè)；如果j這張牌比我新抽到的牌數(shù)值小，我就應(yīng)當(dāng)把新抽到的牌插在j這張牌的右邊。
tmp變量中存儲(chǔ)的是我新抽到的牌。
三、高效排序算法
1.快速排序
- 算法實(shí)現(xiàn)過(guò)程
?先從數(shù)據(jù)序列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)（習(xí)慣取第一個(gè)數(shù)）。
分區(qū)過(guò)程，將比基準(zhǔn)數(shù)小的數(shù)全放到它的左邊,大于或等于它的數(shù)全放到它的右邊。
再對(duì)左右區(qū)間遞歸重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。
- 時(shí)間復(fù)雜度 o(nlogn)
- 代碼實(shí)現(xiàn)
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: # 從右邊開(kāi)始找比tmp小的數(shù)
right -= 1 # right往左走一步
li[left] = li[right] # 把右邊的值寫(xiě)在左邊的空位上
while left < right and li[left] < tmp:
left += 1
li[right] = li[left] # 把左邊的值寫(xiě)在右邊的空位上
li[left] = tmp # 把tmp歸位
return left
def quick_sort(data, left, right):
if left < right: # 說(shuō)明至少兩個(gè)元素
mid = partition(data, left, right) # 說(shuō)明第一個(gè)元素已經(jīng)歸位，mid把列表分成兩部分
quick_sort(data, left, mid - 1) # 遞歸調(diào)用這兩部分
quick_sort(data, mid + 1, right)2.堆排序
- 算法實(shí)現(xiàn)過(guò)程
1. 建立大根堆
2. 得到堆頂元素，為最大元素
3. 去掉堆頂，將堆頂最后一個(gè)元素放到堆頂，此時(shí)可以通過(guò)一次調(diào)整使堆有序
4. 堆頂元素為第二大元素
5. 重復(fù)步驟三，直到堆變空
- 時(shí)間復(fù)雜度 nlg(n)
- 代碼實(shí)現(xiàn)
def sift(li, low, high):
"""
:param li: 列表
:param low: 堆的根部節(jié)點(diǎn)位置(堆頂)
:param high: 堆的最后一個(gè)節(jié)點(diǎn)的位置
"""
i = low # i最開(kāi)始指向根節(jié)點(diǎn)
j = 2 * i + 1 # j開(kāi)始指向根節(jié)點(diǎn)的左孩子
tmp = li[low] # 把堆頂元素存起來(lái)
while j <= high: # 只要j位置有數(shù)則一直循環(huán)
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子比左孩子大，并且要保證右孩子要有(不越界）
j = j+1 # 把就指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一層
j = 2 * i + 1
else: # 說(shuō)明tmp更大，把tmp放在i的位置上
li[i] = tmp # 把tmp防災(zāi)某一級(jí)領(lǐng)導(dǎo)的位置上
break
else:
li[i] = tmp # 把tmp放到葉子節(jié)點(diǎn)上
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):# i表示建堆的時(shí)候調(diào)整的部分的根的下標(biāo)
sift(li, i, n-1) # 建堆完成
for i in range(n-1, -1, -1): # i指向當(dāng)前堆的最后一個(gè)元素
li[0], li[i] = li[i], li[0] # 讓堆頂元素和最后一個(gè)元素做交換
sift(li, 0, i-1) # i-1是新的high- 堆排序的應(yīng)用——topk問(wèn)題
現(xiàn)有n個(gè)數(shù)，設(shè)計(jì)算法得到前K大的數(shù)
解題思路：取列表前K個(gè)元素建立一個(gè)小根堆。堆頂就是目前第K大的數(shù)。依次向后遍歷原列表，對(duì)于列表中的元素，如果小于堆頂，則忽略該元素；如果大于堆頂，則將堆頂更換為該元素，并且對(duì)堆進(jìn)行一次調(diào)整，遍歷列表所有元素后，倒敘彈出堆頂
def sift(li, low, high):
i = low
j = 2 * i + 1
tmp = li[low]
while j <= high:
if j+1 <= high and li[j+1] < li[j]:
j = j+1
if li[j] < tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def topk(li, k):
heap = li[0:k] # 把0到K的數(shù)取出來(lái)
for i in range((k-2)//2, -1, -1):
sift(heap, i, k-1)
for i in range(k, len(li)-1):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, k-1)
for i in range(k - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i - 1)
return heap
?3.歸并排序
- 算法實(shí)現(xiàn)過(guò)程
1.分解：將列表越分越小，直到分成一個(gè)元素 2.終止條件：一個(gè)元素是有序的 3.合并：將兩個(gè)有序列表合并，列表越來(lái)越大。
- ?時(shí)間復(fù)雜度 o(nlgn)
- 代碼實(shí)現(xiàn)
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <=mid and j <= high: # 只要左右兩邊都有數(shù)
if li[i] < li[j]: # 比較i和j指向的兩個(gè)數(shù)的大小關(guān)系
ltmp.append(li[i])
i += 1
else: # j指向的比i指向的大
ltmp.append(li[j])
j += 1
# while循環(huán)結(jié)束的時(shí)候，兩部分肯定有一部分沒(méi)數(shù)了
while i <= mid: # 當(dāng)j沒(méi)有剩余時(shí)
ltmp.append(li[i])
i += 1
while j <= high: # 當(dāng)i沒(méi)有剩余時(shí)
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
def merge_sort(li, low, high):
if low < high: # 至少有兩個(gè)元素，遞歸
mid = (low + high)//2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)四、其他排序算法
1.希爾排序
- 算法實(shí)現(xiàn)過(guò)程
希爾排序是一種分組插入插入排序算法，首先取一個(gè)整數(shù)d1=n/2，將元素分為d1個(gè)組，每組相鄰量元素之間的距離為d1，在各組內(nèi)進(jìn)行直接插入排序；取第二個(gè)整數(shù)d2=d/2，重復(fù)上述分組排序過(guò)程，直到d1=1，即所有元素在同一組內(nèi)進(jìn)行直接插入排序；希爾排序每趟并不使某些元素有序，而是使整體數(shù)據(jù)越來(lái)越接近有序；最后一趟使得所有數(shù)據(jù)有序。
- 時(shí)間復(fù)雜度
希爾排序1的時(shí)間復(fù)雜度討論比較復(fù)雜，并且和選取的gap序列有關(guān)
- 代碼實(shí)現(xiàn)
def insert_sort_gap(li, gap):
for i in range(gap, len(li)):
tmp = li[i]
j = i - gap
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 22.計(jì)數(shù)排序
- 算法實(shí)現(xiàn)過(guò)程
假設(shè)列表中的數(shù)字都在0到100之間，計(jì)算數(shù)字出現(xiàn)的次數(shù)，然后按順序列出這些數(shù)字。
- 時(shí)間復(fù)雜度 o(n)
- 代碼實(shí)現(xiàn)
def count_sort(li, max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)3.計(jì)數(shù)排序的引申——桶排序
- 算法實(shí)現(xiàn)過(guò)程
在計(jì)數(shù)排序中，如果元素的范圍比較大(比如在1到1億之間),我們應(yīng)當(dāng)如何改進(jìn)算法？
桶排序：首先將元素分在不同的桶中，在每個(gè)桶中的元素排序，eg：我有以下這些數(shù)，我講他們按大小放在下面五個(gè)桶中
- 時(shí)間復(fù)雜度?
桶排序的時(shí)間復(fù)雜度取決于數(shù)據(jù)的分布，也就是需要對(duì)不同數(shù)據(jù)排序時(shí)采取不同的分同策略文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-833846.html
- 代碼實(shí)現(xiàn)
def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 創(chuàng)建n個(gè)桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到幾號(hào)桶里
buckets[i].append(var) # var加在桶里面
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sort_li = []
for buc in buckets:
sort_li.extend(buc)
return sort_li4.基數(shù)排序
- 算法實(shí)現(xiàn)過(guò)程
排序過(guò)程中，將元素分層為多個(gè)關(guān)鍵碼進(jìn)行排序（一般按照數(shù)值的個(gè)位、十位、百位、…… 進(jìn)行區(qū)分），多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-833846.html
- 時(shí)間復(fù)雜度 o(kn)
- 代碼實(shí)現(xiàn)
def radix_sort(li):
max_num = max(li)
it = 0
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
digit = (var // 10 ** it) % 10
buckets[digit].append(var)
li.clear()
for buc in buckets:
li.extend(buc)
it += 1
到了這里，關(guān)于探索十大經(jīng)典排序算法之美（基于Python）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
