abstrait：1：快速排序思想：任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一趟快速排序。一趟快速排序的算法是：1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將
1：快速排序
思想：
任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一趟快速排序。
一趟快速排序的算法是：
1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]賦給A[i]；
4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]賦給A[j]；
5）重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。
注意：快速排序不會(huì)直接得到最終結(jié)果，只會(huì)把比k大和比k小的數(shù)分到k的兩邊。（你可以想象一下i和j是兩個(gè)機(jī)器人，數(shù)據(jù)就是大小不一的石頭，先取走i前面的石頭留出回旋的空間，然后他們輪流分別挑選比k大和比k小的石頭扔給對(duì)面，最后在他們中間把取走的那塊石頭放回去，于是比這塊石頭大的全扔給了j那一邊，小的全扔給了i那一邊。只是這次運(yùn)氣好，扔完一次剛好排整齊。）為了得到最后結(jié)果，需要再次對(duì)下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個(gè)數(shù)據(jù)），才能得到正確結(jié)果。
python實(shí)現(xiàn)代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
s.append(random.randint(1,100))
print(s[i]),
#
print("\nbegin")
def partition(inlist,start,end):
i = start
j = end
k = inlist[i]
while i<j:
while i<j and inlist[j]>=k:
j = j-1
inlist[i]=inlist[j]
while i<j and inlist[i]<=k:
i = i+1
inlist[j]=inlist[i]
inlist[i]=k
return i
def quickSort(inlist,start,end):
if start>=end:
return
middle = partition(inlist,start,end)
quickSort(inlist,start,middle-1)
quickSort(inlist,middle+1,end)
quickSort(s,0,len(s)-1)
for i in s:
print "%d " %i,
print("done")2：直接插入排序
思想：
每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小插入到有序表中； 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從前向后掃描，把第三個(gè)數(shù)按大小插入到有序表中；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。
python 代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
s.append(random.randint(1,100))
print(s[i]),
#
print("\nbegin")
j=0
for i in range(1,len(s)):
if s[i]<s[i-1]:
temp = s[i]
j=i-1
while j>=0 and s[j]>temp:
s[j+1]=s[j]
s[j]=temp
j=j-1
for i in s:
print "%d " %i,
print("\ndone")3：冒泡排序
思想：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
python 代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
s.append(random.randint(1,100))
print(s[i]),
#
print("\nbegin")
i = len(s)-1
while i>0:
j=0
for j in range(0,i):
if s[j+1]<s[j]:
temp = s[j]
s[j]=s[j+1]
s[j+1]=temp
j = j+1
i = i-1
for i in s:
print "%d " %i,
print("\ndone")4：桶排序
思想：
假定：輸入是由一個(gè)隨機(jī)過(guò)程產(chǎn)生的[0, 1)區(qū)間上均勻分布的實(shí)數(shù)。將區(qū)間[0, 1)劃分為n個(gè)大小相等的子區(qū)間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個(gè)輸入元素分配到這些桶中，對(duì)桶中元素進(jìn)行排序，然后依次連接桶輸入0 ≤A[1..n] <1輔助數(shù)組B[0..n-1]是一指針數(shù)組，指向桶（鏈表）。
太難懂了，舉個(gè)簡(jiǎn)單的例子：
一年的全國(guó)高考考生人數(shù)為500 萬(wàn)，分?jǐn)?shù)使用標(biāo)準(zhǔn)分，最低100 ，最高900 ，沒(méi)有小數(shù)，你把這500 萬(wàn)元素的數(shù)組排個(gè)序。
我們發(fā)現(xiàn)，這些數(shù)據(jù)都有特殊的條件： 100=<score<=900。那么我們就可以考慮桶排序這樣一個(gè)“投機(jī)取巧”的辦法、讓其在毫秒級(jí)別就完成500萬(wàn)排序。
方法：創(chuàng)建801(900-100)個(gè)桶。將每個(gè)考生的分?jǐn)?shù)丟進(jìn)f(score)=score-100的桶中。這個(gè)過(guò)程從頭到尾遍歷一遍數(shù)據(jù)只需要500W次。然后根據(jù)桶號(hào)大小依次將桶中數(shù)值輸出，即可以得到一個(gè)有序的序列。而且可以很容易的得到100分有***人，501分有***人。
python代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
#10000 numbers,range in (0,100)
s = []
for i in range(0,10000):
s.append(random.randint(0,100))
#print(s[i]),
#
print("\nbegin")
r = {}
for i in range(0,101):
r[i]=[]
for i in s:
r[i].append(i)
f = file("r.txt","w")
for i in range(0,101):
for j in r[i]:
f.write(str(j)+',')
print("\ndone")5：歸并排序
思想：
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)有序的子序列，再把有序的子序列合并為整體有序序列。
python代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
s.append(random.randint(1,100))
print(s[i]),print("\nbegin")
def spli(inlist):
if len(inlist)<=1:
return inlist
num = len(inlist)/2
left = spli(inlist[0:num])
right = spli(inlist[num:])
return sor(left,right)
def sor(left,right):
#print(left)
#print(right)
l = 0
r = 0
result =[]
while l<len(left) and r <len(right):
if left[l]<right[r]:
result.append(left[l])
l =l+1
else:
result.append(right[r])
r = r+1
result = result+right[r:]
result = result+left[l:]
return result
s=spli(s)
for i in s:
print "%d " %i,
print("\ndone")6：堆排序
思想：
1.什么是堆？
堆實(shí)際上是一棵完全二叉樹(shù)，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字。
堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱(chēng)為大頂堆，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱(chēng)為小頂堆。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。
2.堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無(wú)序中選擇最大記錄(最小記錄)變得簡(jiǎn)單。
其基本思想為(大頂堆)：
1)將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；
2)將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];
3)由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。
操作過(guò)程如下：
1)初始化堆：將R[1..n]構(gòu)造為堆；
2)將當(dāng)前無(wú)序區(qū)的堆頂元素R[1]同該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為新的堆。
python 代碼：
#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
count=0
for i in range(0,100):
s.append(random.randint(1,100))
print(s[i]),
#
print("\nbegin")
def heap_sort(inlist):
for start in range((len(inlist)-2)/2,-1,-1):#1：初始化堆：從最底層開(kāi)始建樹(shù)，并且保證是堆
sift_down(inlist,start,len(inlist)-1)
for end in range(len(inlist)-1,0,-1):#2：將堆頂元素與最后一個(gè)元素交換，調(diào)整
inlist[0],inlist[end]=inlist[end],inlist[0]
sift_down(inlist,0,end-1)
return inlist
def sift_down(inlist,start,end):
"""調(diào)整算法：從父節(jié)點(diǎn)、左孩子節(jié)點(diǎn)、右孩子節(jié)點(diǎn)三者中選擇最大者跟父節(jié)點(diǎn)進(jìn)行交換
(交換之后可能造成被交換的孩子節(jié)點(diǎn)不滿足堆的性質(zhì)，
因此每次交換之后要重新對(duì)被交換的孩子節(jié)點(diǎn)進(jìn)行調(diào)整)"""
root = start
while True:
global count
count=count+1
child = 2*root +1#左節(jié)點(diǎn)
if child>end:
break
if child+1<=end and inlist[child]<inlist[child+1]:#左節(jié)點(diǎn)比右節(jié)點(diǎn)小
child = child+1#保證child對(duì)應(yīng)的是左右節(jié)點(diǎn)中最大的
if inlist[root]<inlist[child]:#如果root不是最大，交換
inlist[root],inlist[child]=inlist[child],inlist[root]
root=child
else:
break
heap_sort(s)
for i in s:
print (i),
print("\ndone")
print(count)6種算法比較次數(shù)的比較
隨機(jī)生成10000的數(shù)據(jù)
很容易可以看出：
1：桶排序是最快的，但使用范圍有限，排序的標(biāo)準(zhǔn)和數(shù)據(jù)的屬性是一致的
2：快速排序、歸并排序和堆排序都是NlogN的，但具體還是差別的，隨機(jī)數(shù)據(jù)來(lái)看，比較次數(shù)：歸并《堆《快速
有序序列的影響：
快速排序：有序》》》》（遠(yuǎn)大于）無(wú)序
直接插入：有序《無(wú)序
冒泡：有序《無(wú)序
桶排序：無(wú)差別
歸并：有序《無(wú)序
堆排序：有序》無(wú)序