python实现排序算法_数据结构之（3）python实现排序算法
常用排序與插入算法
冒泡排序
冒泡排序（英語：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序算法的運(yùn)作如下：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序），就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
冒泡排序的分析
交換過程圖示(第一次)：
代碼如下：
defbubble_sort(li):for i in range(len(li) - 1):for j in range(len(li) - i - 1):if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]returnli
list1= [15, 66, 20, 350, 464, 88, 995, 100]print(bubble_sort(list1))
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束。）
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：穩(wěn)定
冒泡排序的演示
效果：
選擇排序
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
選擇排序分析
排序過程：
紅色表示當(dāng)前最小值，黃色表示已排序序列，藍(lán)色表示當(dāng)前位置。
defselection_sort(alist):
n=len(alist)#需要進(jìn)行n-1次選擇操作
for i in range(n-1):#記錄最小位置
min_index=i#從i+1位置到末尾選擇出最小數(shù)據(jù)
for j in range(i+1, n):if alist[j]
min_index=j#如果選擇出的數(shù)據(jù)不在正確位置，進(jìn)行交換
if min_index !=i:
alist[i], alist[min_index]=alist[min_index], alist[i]
alist= [54,226,93,17,77,31,44,55,20]
selection_sort(alist)print(alist)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(n2)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）
選擇排序演示
插入排序
插入排序（英語：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
插入排序分析
definsert_sort(alist):#從第二個(gè)位置，即下標(biāo)為1的元素開始向前插入
for i in range(1, len(alist)):#從第i個(gè)元素開始向前比較，如果小于前一個(gè)元素，交換位置
for j in range(i, 0, -1):if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
alist= [54,26,93,17,77,31,44,55,20]
insert_sort(alist)print(alist)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：穩(wěn)定
插入排序演示
快速排序
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
步驟為：
從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡?#xff08;iteration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
快速排序的分析
defquick_sort(alist, start, end):"""快速排序"""
#遞歸的退出條件
if start >=end:return
#設(shè)定起始元素為要尋找位置的基準(zhǔn)元素
mid=alist[start]#low為序列左邊的由左向右移動(dòng)的游標(biāo)
low=start#high為序列右邊的由右向左移動(dòng)的游標(biāo)
high=endwhile low
while low < high and alist[high] >=mid:
high-= 1
#將high指向的元素放到low的位置上
alist[low]=alist[high]#如果low與high未重合，low指向的元素比基準(zhǔn)元素小，則low向右移動(dòng)
while low < high and alist[low]
low+= 1
#將low指向的元素放到high的位置上
alist[high]=alist[low]#退出循環(huán)后，low與high重合，此時(shí)所指位置為基準(zhǔn)元素的正確位置
#將基準(zhǔn)元素放到該位置
alist[low]=mid#對(duì)基準(zhǔn)元素左邊的子序列進(jìn)行快速排序
quick_sort(alist, start, low-1)#對(duì)基準(zhǔn)元素右邊的子序列進(jìn)行快速排序
quick_sort(alist, low+1, end)
alist= [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)print(alist)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
從一開始快速排序平均需要花費(fèi)O(n log n)時(shí)間的描述并不明顯。但是不難觀察到的是分區(qū)運(yùn)算，數(shù)組的元素都會(huì)在每次循環(huán)中走訪過一次，使用O(n)的時(shí)間。在使用結(jié)合（concatenation）的版本中，這項(xiàng)運(yùn)算也是O(n)。
在最好的情況，每次我們運(yùn)行一次分區(qū)，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段。這個(gè)意思就是每次遞歸調(diào)用處理一半大小的數(shù)列。因此，在到達(dá)大小為一的數(shù)列前，我們只要作log n次嵌套的調(diào)用。這個(gè)意思就是調(diào)用樹的深度是O(log n)。但是在同一層次結(jié)構(gòu)的兩個(gè)程序調(diào)用中，不會(huì)處理到原來數(shù)列的相同部分；因此，程序調(diào)用的每一層次結(jié)構(gòu)總共全部?jī)H需要O(n)的時(shí)間（每個(gè)調(diào)用有某些共同的額外耗費(fèi)，但是因?yàn)樵诿恳粚哟谓Y(jié)構(gòu)僅僅只有O(n)個(gè)調(diào)用，這些被歸納在O(n)系數(shù)中）。結(jié)果是這個(gè)算法僅需使用O(n log n)時(shí)間。
快速排序演示
希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
希爾排序過程
希爾排序的基本思想是：將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過程，不過每次用更長(zhǎng)的列（步長(zhǎng)更長(zhǎng)了，列數(shù)更少了）來進(jìn)行。最后整個(gè)表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進(jìn)行排序。
例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長(zhǎng)為5開始進(jìn)行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣(豎著的元素是步長(zhǎng)組成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對(duì)每列進(jìn)行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數(shù)字，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時(shí)10已經(jīng)移至正確位置了，然后再以3為步長(zhǎng)進(jìn)行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)?#xff1a;
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）
希爾排序的分析
defshell_sort(alist):
n=len(alist)#初始步長(zhǎng)
gap= n / 2
while gap >0:#按步長(zhǎng)進(jìn)行插入排序
for i inrange(gap, n):
j=i#插入排序
while j>=gap and alist[j-gap] >alist[j]:
alist[j-gap], alist[j] = alist[j], alist[j-gap]
j-=gap#得到新的步長(zhǎng)
gap= gap / 2alist= [54,26,93,17,77,31,44,55,20]
shell_sort(alist)print(alist)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定想：不穩(wěn)定
希爾排序演示
歸并排序
歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
將數(shù)組分解最小之后，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。然后再比較，直至一個(gè)數(shù)組為空，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可。
歸并排序的分析
defmerge(li, low, mid, high):
i=low
j= mid + 1ltmp=[]while i <= mid and j <=high:if li[i]
ltmp.append(li[i])
i+= 1
else:
ltmp.append(li[j])
j+= 1
while i <=mid:
ltmp.append(li[i])
i+= 1
while j <=high:
ltmp.append(li[j])
j+= 1li[low:high+1] =ltmpdef_mergesort(li, low, high):if low
mid= (low + high) // 2_mergesort(li,low, mid)
_mergesort(li, mid+1, high)
merge(li, low, mid, high)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(nlogn)
穩(wěn)定性：穩(wěn)定
堆排序
堆
在這里首先要先解釋一下什么是堆，堆棧是計(jì)算機(jī)的兩種最基本的數(shù)據(jù)結(jié)構(gòu)。堆的特點(diǎn)就是FIFO(first in first out)先進(jìn)先出，這里的話我覺得可以理解成樹的結(jié)構(gòu)。堆在接收數(shù)據(jù)的時(shí)候先接收的數(shù)據(jù)會(huì)被先彈出。
棧的特性正好與堆相反，是屬于FILO(first in/last out)先進(jìn)后出的類型。棧處于一級(jí)緩存而堆處于二級(jí)緩存中。這個(gè)不是本文重點(diǎn)所以不做過多展開。
堆排序節(jié)點(diǎn)訪問和操作定義
堆節(jié)點(diǎn)的訪問
在這里我們借用wiki的定義來說明：
通常堆是通過一維數(shù)組來實(shí)現(xiàn)的。在陣列起始位置為0的情況中
(1)父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置(2*i+1);
(2)父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置(2*i+2);
(3)子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置floor((i-1)/2);
堆操作
堆可以分為大根堆和小根堆，這里用最大堆的情況來定義操作:
(1)最大堆調(diào)整(MAX_Heapify):將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)。這是核心步驟，在建堆和堆排序都會(huì)用到。比較i的根節(jié)點(diǎn)和與其所對(duì)應(yīng)i的孩子節(jié)點(diǎn)的值。當(dāng)i根節(jié)點(diǎn)的值比左孩子節(jié)點(diǎn)的值要小的時(shí)候，就把i根節(jié)點(diǎn)和左孩子節(jié)點(diǎn)所對(duì)應(yīng)的值交換，當(dāng)i根節(jié)點(diǎn)的值比右孩子的節(jié)點(diǎn)所對(duì)應(yīng)的值要小的時(shí)候，就把i根節(jié)點(diǎn)和右孩子節(jié)點(diǎn)所對(duì)應(yīng)的值交換。然后再調(diào)用堆調(diào)整這個(gè)過程，可見這是一個(gè)遞歸的過程。
(2)建立最大堆(Build_Max_Heap):將堆所有數(shù)據(jù)重新排序。建堆的過程其實(shí)就是不斷做最大堆調(diào)整的過程，從len/2出開始調(diào)整，一直比到第一個(gè)節(jié)點(diǎn)。
(3)堆排序(HeapSort):移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。堆排序是利用建堆和堆調(diào)整來進(jìn)行的。首先先建堆，然后將堆的根節(jié)點(diǎn)選出與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換，然后將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)做堆調(diào)整的過程。直到將所有的節(jié)點(diǎn)取出，對(duì)于n個(gè)數(shù)我們只需要做n-1次操作。
這里用網(wǎng)上的一張直觀圖來感受一下
defsift(data, low, high):
i=low
j= 2 * i + 1tmp=data[i]while j <= high: #只要沒到子樹的最后
if j+1 <= high and data[j] < data[j + 1]: #如果有右孩子且比左孩子大
j+= 1 #就把j指向右孩子
if tmp < data[j]:#如果領(lǐng)導(dǎo)不能干
data[i] = data[j] #小領(lǐng)導(dǎo)上位
i =j
j= 2 * i + 1
else:breakdata[i]=tmpdefheap_sort(data):
n=len(data)for i in range(n // 2 - 1, -1, -1):
sift(data, i, n- 1)for i in range(n - 1, -1, -1):
data[0], data[i]=data[i], data[0]
sift(data, 0, i- 1)
查找算法
搜索是在一個(gè)項(xiàng)目集合中找到一個(gè)特定項(xiàng)目的算法過程。搜索通常的答案是真的或假的，因?yàn)樵擁?xiàng)目是否存在。 搜索的幾種常見方法：順序查找、二分法查找、二叉樹查找、哈希查找
二分法查找
二分查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。
二分法查找實(shí)現(xiàn)
（非遞歸實(shí)現(xiàn)）
defbinary_search(alist, item):
first=0
last= len(alist)-1
while first<=last:
midpoint= (first + last)/2
if alist[midpoint] ==item:returnTrueelif item
last= midpoint-1
else:
first= midpoint+1
returnFalse
testlist= [0, 1, 2, 8, 13, 17, 19, 32, 42,]print(binary_search(testlist, 3))print(binary_search(testlist, 13))
（遞歸實(shí)現(xiàn)）defbinary_search(alist, item):if len(alist) ==0:returnFalseelse:
midpoint= len(alist)//2
if alist[midpoint]==item:returnTrueelse:if item
testlist= [0, 1, 2, 8, 13, 17, 19, 32, 42,]print(binary_search(testlist, 3))print(binary_search(testlist, 13))
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(1)
最壞時(shí)間復(fù)雜度：O(logn)
python
算法時(shí)間復(fù)雜度總結(jié)
總結(jié)
以上是生活随笔為你收集整理的python实现排序算法_数据结构之（3）python实现排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： dataset__getitem___[
- 下一篇： python计算短时自相关函数 音频信号