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