三大查找方法
順序查找啦吧，二分法查找（折半查找），分塊查找
順序查找的基本思想：
從表的一端開(kāi)始楣号，順序掃描表叼耙，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值（假定為a）相比較腕窥，若當(dāng)前結(jié)點(diǎn)關(guān)鍵字與a相等，則查找成功筛婉；若掃描結(jié)束后簇爆，仍未找到關(guān)鍵字等于a的結(jié)點(diǎn)，則查找失敗爽撒。
說(shuō)白了就是入蛆，從頭到尾，一個(gè)一個(gè)地比硕勿，找著相同的就成功哨毁，找不到就失敗。很明顯的缺點(diǎn)就是查找效率低源武。
適用于線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)扼褪。
計(jì)算平均查找長(zhǎng)度。
例如上表软能，查找1迎捺，需要1次举畸，查找2需要2次查排，依次往下推，可知查找16需要16次抄沮，
可以看出跋核，我們只要將這些查找次數(shù)求和（我們初中學(xué)的，上底加下底乘以高除以2）叛买，然后除以結(jié)點(diǎn)數(shù)砂代，即為平均查找長(zhǎng)度。
設(shè)n=節(jié)點(diǎn)數(shù)
平均查找長(zhǎng)度 =（n+1）/2
二分法查找（折半查找）的基本思想：
前提：
（1）確定該區(qū)間的中點(diǎn)位置：mid =（low+high）/2
min代表區(qū)間中間的結(jié)點(diǎn)的位置率挣，low代表區(qū)間最左結(jié)點(diǎn)位置刻伊，high代表區(qū)間最右結(jié)點(diǎn)位置
（2）將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功捶箱，否則確定新的查找區(qū)間：
如果R[mid].key>a智什，則由表的有序性可知，R[mid].key右側(cè)的值都大于a丁屎，所以等于a的關(guān)鍵字如果存在荠锭，必然在R[mid].key左邊的表中。這時(shí)high=mid-1
如果R[mid].key<a,則等于a的關(guān)鍵字如果存在晨川，必然在R[mid].key右邊的表中证九。這時(shí)low=mid
如果R[mid].key=a，則查找成功共虑。
（3）下一次查找針對(duì)新的查找區(qū)間愧怜，重復(fù)步驟（1）和（2）
（4）在查找過(guò)程中，low逐步增加妈拌，high逐步減少叫搁，如果high<low，則查找失敗供炎。
/**
* @param $x
* @param $a
* @param $lower
* @param $high
* @return bool|int
*
* 二分查找,需要數(shù)組是一個(gè)有序數(shù)組
* 遞歸實(shí)現(xiàn)
*/
private function binRecursive($x, &$a, $lower = 0, $high = 11)
{
//$lower開(kāi)始位置 $high結(jié)束位置
//采用二分法查找
$c = count($a);
if ($high > $c) {
return false;
}
if ($lower <= $high) {
$middle = intval(($lower + $high) / 2);
if ($a[$middle] == $x) {
return $middle;
} elseif ($a[$middle] < $x) {//在后半段里查
return $this->binSearchRecursive($x, $a, $middle + 1, $high);
} else {//在前半段里查
return $this->binSearchRecursive($x, $a, $lower, $middle - 1);
}
} else {
return false;
}
}
平均查找長(zhǎng)度=Log2(n+1)-1
注：雖然二分法查找的效率高渴逻，但是要將表按關(guān)鍵字排序。而排序本身是一種很費(fèi)時(shí)的運(yùn)算音诫，所以二分法比較適用于順序存儲(chǔ)結(jié)構(gòu)惨奕。為保持表的有序性，在順序結(jié)構(gòu)中插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)竭钝。因此梨撞，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)而又經(jīng)常需要查找的線性表。
分塊查找的基本思想：
二分查找表使分塊有序的線性表和索引表（抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成索引表）組成香罐，由于表是分塊有序的卧波，所以索引表是一個(gè)遞增有序表，因此采用順序或二分查找索引表庇茫，以確定待查結(jié)點(diǎn)在哪一塊港粱，由于塊內(nèi)無(wú)序，只能用順序查找旦签。
設(shè)表共n個(gè)結(jié)點(diǎn)查坪，分b塊，s=n/b
(分塊查找索引表)平均查找長(zhǎng)度=Log2（n/s+1）+s/2
(順序查找索引表)平均查找長(zhǎng)度=(S2+2S+n)/(2S)
注：分塊查找的優(yōu)點(diǎn)是在表中插入或刪除一個(gè)記錄時(shí)宁炫，只要找到該記錄所屬塊偿曙，就在該塊中進(jìn)行插入或刪除運(yùn)算（因塊內(nèi)無(wú)序，所以不需要大量移動(dòng)記錄）羔巢。它主要代價(jià)是增加一個(gè)輔助數(shù)組的存儲(chǔ)控件和將初始表分塊排序的運(yùn)算望忆。
它的性能介于順序查找和二分查找之間罩阵。
八大排序
數(shù)據(jù)結(jié)構(gòu)常見(jiàn)的八大排序算法，他們之間關(guān)系如下：
排序算法.png
他們的性能比較：
性能比較.png
下面启摄，利用Python分別將他們進(jìn)行實(shí)現(xiàn)永脓。
直接插入排序
- 算法思想：
直接插入排序.gif
直接插入排序的核心思想就是：將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較，如果選擇的元素比已排序的元素小鞋仍，則交換常摧，直到全部元素都比較過(guò)。
因此威创，從上面的描述中我們可以發(fā)現(xiàn)落午，直接插入排序可以用兩個(gè)循環(huán)完成：
- 第一層循環(huán)：遍歷待比較的所有數(shù)組元素
- 第二層循環(huán)：將本輪選擇的元素(selected)與已經(jīng)排好序的元素(ordered)相比較。
如果：selected > ordered肚豺，那么將二者交換
- 代碼實(shí)現(xiàn)
#直接插入排序
def insert_sort(L):
#遍歷數(shù)組中的所有元素溃斋，其中0號(hào)索引元素默認(rèn)已排序，因此從1開(kāi)始
for x in range(1,len(L)):
#將該元素與已排序好的前序數(shù)組依次比較吸申，如果該元素小梗劫，則交換
#range(x-1,-1,-1):從x-1倒序循環(huán)到0
for i in range(x-1,-1,-1):
#判斷：如果符合條件則交換
if L[i] > L[i+1]:
temp = L[i+1]
L[i+1] = L[i]
L[i] = temp
希爾排序
- 算法思想：
希爾排序.png
希爾排序的算法思想：將待排序數(shù)組按照步長(zhǎng)gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序截碴；每次將gap折半減小梳侨，循環(huán)上述操作；當(dāng)gap=1時(shí)日丹，利用直接插入走哺，完成排序。
同樣的：從上面的描述中我們可以發(fā)現(xiàn)：希爾排序的總體實(shí)現(xiàn)應(yīng)該由三個(gè)循環(huán)完成：
- 第一層循環(huán)：將gap依次折半哲虾，對(duì)序列進(jìn)行分組丙躏，直到gap=1
- 第二、三層循環(huán)：也即直接插入排序所需要的兩次循環(huán)束凑。具體描述見(jiàn)上晒旅。
- 代碼實(shí)現(xiàn)：
#希爾排序
def insert_shell(L):
#初始化gap值，此處利用序列長(zhǎng)度的一般為其賦值
gap = (int)(len(L)/2)
#第一層循環(huán)：依次改變gap值對(duì)列表進(jìn)行分組
while (gap >= 1):
#下面：利用直接插入排序的思想對(duì)分組數(shù)據(jù)進(jìn)行排序
#range(gap,len(L)):從gap開(kāi)始
for x in range(gap,len(L)):
#range(x-gap,-1,-gap):從x-gap開(kāi)始與選定元素開(kāi)始倒序比較汪诉，每個(gè)比較元素之間間隔gap
for i in range(x-gap,-1,-gap):
#如果該組當(dāng)中兩個(gè)元素滿足交換條件废恋，則進(jìn)行交換
if L[i] > L[i+gap]:
temp = L[i+gap]
L[i+gap] = L[i]
L[i] =temp
#while循環(huán)條件折半
gap = (int)(gap/2)
簡(jiǎn)單選擇排序
- 算法思想
簡(jiǎn)單選擇排序.gif
簡(jiǎn)單選擇排序的基本思想：比較+交換。
- 從待排序序列中摩瞎，找到關(guān)鍵字最小的元素拴签；
- 如果最小元素不是待排序序列的第一個(gè)元素，將其和第一個(gè)元素互換旗们；
- 從余下的 N - 1 個(gè)元素中，找出關(guān)鍵字最小的元素构灸，重復(fù)(1)上渴、(2)步岸梨，直到排序結(jié)束。
因此我們可以發(fā)現(xiàn)稠氮，簡(jiǎn)單選擇排序也是通過(guò)兩層循環(huán)實(shí)現(xiàn)曹阔。
第一層循環(huán)：依次遍歷序列當(dāng)中的每一個(gè)元素
第二層循環(huán)：將遍歷得到的當(dāng)前元素依次與余下的元素進(jìn)行比較，符合最小元素的條件隔披，則交換赃份。
- 代碼實(shí)現(xiàn)
# 簡(jiǎn)單選擇排序
def select_sort(L):
#依次遍歷序列中的每一個(gè)元素
for x in range(0,len(L)):
#將當(dāng)前位置的元素定義此輪循環(huán)當(dāng)中的最小值
minimum = L[x]
#將該元素與剩下的元素依次比較尋找最小元素
for i in range(x+1,len(L)):
if L[i] < minimum:
temp = L[i];
L[i] = minimum;
minimum = temp
#將比較后得到的真正的最小值賦值給當(dāng)前位置
L[x] = minimum
堆排序
堆的概念
堆：本質(zhì)是一種數(shù)組對(duì)象。特別重要的一點(diǎn)性質(zhì)：<b>任意的葉子節(jié)點(diǎn)小于（或大于）它所有的父節(jié)點(diǎn)</b>奢米。對(duì)此抓韩，又分為大頂堆和小頂堆，大頂堆要求節(jié)點(diǎn)的元素都要大于其孩子鬓长，小頂堆要求節(jié)點(diǎn)元素都小于其左右孩子谒拴，兩者對(duì)左右孩子的大小關(guān)系不做任何要求。
利用堆排序涉波，就是基于大頂堆或者小頂堆的一種排序方法英上。下面，我們通過(guò)大頂堆來(lái)實(shí)現(xiàn)啤覆。-
基本思想：
堆排序可以按照以下步驟來(lái)完成：- 首先將序列構(gòu)建稱為大頂堆苍日；
（這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點(diǎn)的元素一定是當(dāng)前序列的最大值）
- 首先將序列構(gòu)建稱為大頂堆苍日；
構(gòu)建大頂堆.png
取出當(dāng)前大頂堆的根節(jié)點(diǎn)，將其與序列末尾元素進(jìn)行交換窗声；
（此時(shí)：序列末尾的元素為已排序的最大值易遣；由于交換了元素，當(dāng)前位于根節(jié)點(diǎn)的堆并不一定滿足大頂堆的性質(zhì)）對(duì)交換后的n-1個(gè)序列元素進(jìn)行調(diào)整嫌佑，使其滿足大頂堆的性質(zhì)豆茫；
Paste_Image.png
- 重復(fù)2.3步驟，直至堆中只有1個(gè)元素為止
- 代碼實(shí)現(xiàn)：
#-------------------------堆排序--------------------------------
#**********獲取左右葉子節(jié)點(diǎn)**********
def LEFT(i):
return 2*i + 1
def RIGHT(i):
return 2*i + 2
#********** 調(diào)整大頂堆 **********
#L:待調(diào)整序列 length: 序列長(zhǎng)度 i:需要調(diào)整的結(jié)點(diǎn)
def adjust_max_heap(L,length,i):
#定義一個(gè)int值保存當(dāng)前序列最大值的下標(biāo)
largest = i
#執(zhí)行循環(huán)操作：兩個(gè)任務(wù)：1 尋找最大值的下標(biāo)屋摇；2.最大值與父節(jié)點(diǎn)交換
while (1):
#獲得序列左右葉子節(jié)點(diǎn)的下標(biāo)
left,right = LEFT(i),RIGHT(i)
#當(dāng)左葉子節(jié)點(diǎn)的下標(biāo)小于序列長(zhǎng)度 并且 左葉子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)時(shí)揩魂，將左葉子節(jié)點(diǎn)的下標(biāo)賦值給largest
if (left < length) and (L[left] > L[i]):
largest = left
print('左葉子節(jié)點(diǎn)')
else:
largest = i
#當(dāng)右葉子節(jié)點(diǎn)的下標(biāo)小于序列長(zhǎng)度 并且 右葉子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)時(shí)，將右葉子節(jié)點(diǎn)的下標(biāo)值賦值給largest
if (right < length) and (L[right] > L[largest]):
largest = right
print('右葉子節(jié)點(diǎn)')
#如果largest不等于i 說(shuō)明當(dāng)前的父節(jié)點(diǎn)不是最大值炮温，需要交換值
if (largest != i):
temp = L[i]
L[i] = L[largest]
L[largest] = temp
i = largest
print(largest)
continue
else:
break
#********** 建立大頂堆 **********
def build_max_heap(L):
length = len(L)
for x in range((int)((length-1)/2),-1,-1):
adjust_max_heap(L,length,x)
#********** 堆排序 **********
def heap_sort(L):
#先建立大頂堆火脉，保證最大值位于根節(jié)點(diǎn)；并且父節(jié)點(diǎn)的值大于葉子結(jié)點(diǎn)
build_max_heap(L)
#i：當(dāng)前堆中序列的長(zhǎng)度.初始化為序列的長(zhǎng)度
i = len(L)
#執(zhí)行循環(huán)：1. 每次取出堆頂元素置于序列的最后(len-1,len-2,len-3...)
# 2. 調(diào)整堆柒啤，使其繼續(xù)滿足大頂堆的性質(zhì)倦挂，注意實(shí)時(shí)修改堆中序列的長(zhǎng)度
while (i > 0):
temp = L[i-1]
L[i-1] = L[0]
L[0] = temp
#堆中序列長(zhǎng)度減1
i = i-1
#調(diào)整大頂堆
adjust_max_heap(L,i,0)
冒泡排序
- 基本思想
冒泡排序.gif
冒泡排序思路比較簡(jiǎn)單：
- 將序列當(dāng)中的左右元素，依次比較担巩，保證右邊的元素始終大于左邊的元素方援；
（ 第一輪結(jié)束后，序列最后一個(gè)元素一定是當(dāng)前序列的最大值涛癌；） - 對(duì)序列當(dāng)中剩下的n-1個(gè)元素再次執(zhí)行步驟1犯戏。
- 對(duì)于長(zhǎng)度為n的序列送火，一共需要執(zhí)行n-1輪比較
（利用while循環(huán)可以減少執(zhí)行次數(shù)）
*代碼實(shí)現(xiàn)
#冒泡排序
def bubble_sort(L):
length = len(L)
#序列長(zhǎng)度為length，需要執(zhí)行l(wèi)ength-1輪交換
for x in range(1,length):
#對(duì)于每一輪交換先匪，都將序列當(dāng)中的左右元素進(jìn)行比較
#每輪交換當(dāng)中种吸，由于序列最后的元素一定是最大的，因此每輪循環(huán)到序列未排序的位置即可
for i in range(0,length-x):
if L[i] > L[i+1]:
temp = L[i]
L[i] = L[i+1]
L[i+1] = temp
快速排序
- 算法思想：
快速排序.gif
快速排序的基本思想：挖坑填數(shù)+分治法
- 從序列當(dāng)中選擇一個(gè)基準(zhǔn)數(shù)(pivot)
在這里我們選擇序列當(dāng)中第一個(gè)數(shù)最為基準(zhǔn)數(shù) - 將序列當(dāng)中的所有數(shù)依次遍歷呀非，比基準(zhǔn)數(shù)大的位于其右側(cè)坚俗，比基準(zhǔn)數(shù)小的位于其左側(cè)
- 重復(fù)步驟1.2，直到所有子集當(dāng)中只有一個(gè)元素為止岸裙。
用偽代碼描述如下：
1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]猖败。
2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑a[i]中哥桥。
3．i++由前向后找比它大的數(shù)辙浑，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中。
4．再重復(fù)執(zhí)行2拟糕，3二步判呕，直到i==j，將基準(zhǔn)數(shù)填入a[i]中
- 代碼實(shí)現(xiàn)：
#快速排序
#L：待排序的序列送滞；start排序的開(kāi)始index,end序列末尾的index
#對(duì)于長(zhǎng)度為length的序列：start = 0;end = length-1
def quick_sort(L,start,end):
if start < end:
i , j , pivot = start , end , L[start]
while i < j:
#從右開(kāi)始向左尋找第一個(gè)小于pivot的值
while (i < j) and (L[j] >= pivot):
j = j-1
#將小于pivot的值移到左邊
if (i < j):
L[i] = L[j]
i = i+1
#從左開(kāi)始向右尋找第一個(gè)大于pivot的值
while (i < j) and (L[i] < pivot):
i = i+1
#將大于pivot的值移到右邊
if (i < j):
L[j] = L[i]
j = j-1
#循環(huán)結(jié)束后侠草，說(shuō)明 i=j，此時(shí)左邊的值全都小于pivot,右邊的值全都大于pivot
#pivot的位置移動(dòng)正確犁嗅，那么此時(shí)只需對(duì)左右兩側(cè)的序列調(diào)用此函數(shù)進(jìn)一步排序即可
#遞歸調(diào)用函數(shù)：依次對(duì)左側(cè)序列：從0 ~ i-1//右側(cè)序列：從i+1 ~ end
L[i] = pivot
#左側(cè)序列繼續(xù)排序
quick_sort(L,start,i-1)
#右側(cè)序列繼續(xù)排序
quick_sort(L,i+1,end)
歸并排序
- 算法思想：
歸并排序.gif
- 歸并排序是建立在歸并操作上的一種有效的排序算法边涕，該算法是采用分治法的一個(gè)典型的應(yīng)用。它的基本操作是：將已有的子序列合并褂微，達(dá)到完全有序的序列功蜓；即先使每個(gè)子序列有序，再使子序列段間有序宠蚂。
- 歸并排序其實(shí)要做兩件事：
- 分解----將序列每次折半拆分
- 合并----將劃分后的序列段兩兩排序合并
因此式撼，歸并排序?qū)嶋H上就是兩個(gè)操作，拆分+合并
- 如何合并求厕？
L[first...mid]為第一段著隆，L[mid+1...last]為第二段，并且兩端已經(jīng)有序呀癣，現(xiàn)在我們要將兩端合成達(dá)到L[first...last]并且也有序美浦。
- 首先依次從第一段與第二段中取出元素比較，將較小的元素賦值給temp[]
- 重復(fù)執(zhí)行上一步项栏，當(dāng)某一段賦值結(jié)束浦辨，則將另一段剩下的元素賦值給temp[]
- 此時(shí)將temp[]中的元素復(fù)制給L[]，則得到的L[first...last]有序
- 如何分解忘嫉？
在這里荤牍，我們采用遞歸的方法案腺，首先將待排序列分成A,B兩組庆冕；然后重復(fù)對(duì)A康吵、B序列
分組；直到分組后組內(nèi)只有一個(gè)元素访递，此時(shí)我們認(rèn)為組內(nèi)所有元素有序晦嵌，則分組結(jié)束。
- 代碼實(shí)現(xiàn)
# 歸并排序
#這是合并的函數(shù)
# 將序列L[first...mid]與序列L[mid+1...last]進(jìn)行合并
def mergearray(L,first,mid,last,temp):
#對(duì)i,j,k分別進(jìn)行賦值
i,j,k = first,mid+1,0
#當(dāng)左右兩邊都有數(shù)時(shí)進(jìn)行比較拷姿，取較小的數(shù)
while (i <= mid) and (j <= last):
if L[i] <= L[j]:
temp[k] = L[i]
i = i+1
k = k+1
else:
temp[k] = L[j]
j = j+1
k = k+1
#如果左邊序列還有數(shù)
while (i <= mid):
temp[k] = L[i]
i = i+1
k = k+1
#如果右邊序列還有數(shù)
while (j <= last):
temp[k] = L[j]
j = j+1
k = k+1
#將temp當(dāng)中該段有序元素賦值給L待排序列使之部分有序
for x in range(0,k):
L[first+x] = temp[x]
# 這是分組的函數(shù)
def merge_sort(L,first,last,temp):
if first < last:
mid = (int)((first + last) / 2)
#使左邊序列有序
merge_sort(L,first,mid,temp)
#使右邊序列有序
merge_sort(L,mid+1,last,temp)
#將兩個(gè)有序序列合并
mergearray(L,first,mid,last,temp)
# 歸并排序的函數(shù)
def merge_sort_array(L):
#聲明一個(gè)長(zhǎng)度為len(L)的空列表
temp = len(L)*[None]
#調(diào)用歸并排序
merge_sort(L,0,len(L)-1,temp)
基數(shù)排序
- 算法思想
基數(shù)排序.gif
- 基數(shù)排序：通過(guò)序列中各個(gè)元素的值惭载，對(duì)排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來(lái)實(shí)現(xiàn)排序。
分配：我們將L[i]中的元素取出响巢，首先確定其個(gè)位上的數(shù)字描滔，根據(jù)該數(shù)字分配到與之序號(hào)相同的桶中
收集：當(dāng)序列中所有的元素都分配到對(duì)應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[ ]
對(duì)新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位踪古、百位...直到分配完該序列中的最高位含长，則排序結(jié)束 - 根據(jù)上述“基數(shù)排序”的展示，我們可以清楚的看到整個(gè)實(shí)現(xiàn)的過(guò)程
- 代碼實(shí)現(xiàn)
#************************基數(shù)排序****************************
#確定排序的次數(shù)
#排序的順序跟序列中最大數(shù)的位數(shù)相關(guān)
def radix_sort_nums(L):
maxNum = L[0]
#尋找序列中的最大數(shù)
for x in L:
if maxNum < x:
maxNum = x
#確定序列中的最大元素的位數(shù)
times = 0
while (maxNum > 0):
maxNum = (int)(maxNum/10)
times = times+1
return times
#找到num從低到高第pos位的數(shù)據(jù)
def get_num_pos(num,pos):
return ((int)(num/(10**(pos-1))))%10
#基數(shù)排序
def radix_sort(L):
count = 10*[None] #存放各個(gè)桶的數(shù)據(jù)統(tǒng)計(jì)個(gè)數(shù)
bucket = len(L)*[None] #暫時(shí)存放排序結(jié)果
#從低位到高位依次執(zhí)行循環(huán)
for pos in range(1,radix_sort_nums(L)+1):
#置空各個(gè)桶的數(shù)據(jù)統(tǒng)計(jì)
for x in range(0,10):
count[x] = 0
#統(tǒng)計(jì)當(dāng)前該位(個(gè)位伏穆，十位拘泞，百位....)的元素?cái)?shù)目
for x in range(0,len(L)):
#統(tǒng)計(jì)各個(gè)桶將要裝進(jìn)去的元素個(gè)數(shù)
j = get_num_pos(int(L[x]),pos)
count[j] = count[j]+1
#count[i]表示第i個(gè)桶的右邊界索引
for x in range(1,10):
count[x] = count[x] + count[x-1]
#將數(shù)據(jù)依次裝入桶中
for x in range(len(L)-1,-1,-1):
#求出元素第K位的數(shù)字
j = get_num_pos(L[x],pos)
#放入對(duì)應(yīng)的桶中，count[j]-1是第j個(gè)桶的右邊界索引
bucket[count[j]-1] = L[x]
#對(duì)應(yīng)桶的裝入數(shù)據(jù)索引-1
count[j] = count[j]-1
# 將已分配好的桶中數(shù)據(jù)再倒出來(lái)枕扫，此時(shí)已是對(duì)應(yīng)當(dāng)前位數(shù)有序的表
for x in range(0,len(L)):
L[x] = bucket[x]
后記
寫完之后運(yùn)行了一下時(shí)間比較：
- 1w個(gè)數(shù)據(jù)時(shí)：
直接插入排序:11.615608
希爾排序:13.012008
簡(jiǎn)單選擇排序:3.645136000000001
堆排序:0.09587900000000005
冒泡排序:6.687218999999999
#****************************************************
快速排序:9.999999974752427e-07
#快速排序有誤：實(shí)際上并未執(zhí)行
#RecursionError: maximum recursion depth exceeded in comparison
#****************************************************
歸并排序:0.05638299999999674
基數(shù)排序:0.08150400000000246
- 10w個(gè)數(shù)據(jù)時(shí)：
直接插入排序:1233.581131
希爾排序:1409.8012320000003
簡(jiǎn)單選擇排序:466.66974500000015
堆排序:1.2036720000000969
冒泡排序:751.274449
#****************************************************
快速排序:1.0000003385357559e-06
#快速排序有誤：實(shí)際上并未執(zhí)行
#RecursionError: maximum recursion depth exceeded in comparison
#****************************************************
歸并排序:0.8262230000000272
基數(shù)排序:1.1162899999999354
從運(yùn)行結(jié)果上來(lái)看陪腌，堆排序、歸并排序烟瞧、基數(shù)排序真的快诗鸭。
對(duì)于快速排序迭代深度超過(guò)的問(wèn)題，可以將考慮將快排通過(guò)非遞歸的方式進(jìn)行實(shí)現(xiàn)参滴。
參考：
簡(jiǎn)書(shū)用戶 【LeeLom】的文章 《數(shù)據(jù)結(jié)構(gòu)常見(jiàn)的八大排序算法（詳細(xì)整理）》
