常用排序算法比較與分析

1、常用排序算法比較與分析 一、常用排序算法簡述下面主要從排序算法的基本概念、原理出發(fā),分別從算法的時間復(fù)雜度、空間復(fù)雜度、算法的穩(wěn)定性和速度等方面進行分析比較。依據(jù)待排序的問題大小(記錄數(shù)量 n)的不同，排序過程中需要的存儲器空間也不同，由此將排序算法分為兩大類：【內(nèi)排序】、【外排序】。內(nèi)排序：指排序時數(shù)據(jù)元素全部存放在計算機的隨機存儲器RAM中。外排序：待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中還需要對外存進行訪問的排序過程。先了解一下常見排序算法的分類關(guān)系(見圖1-1)圖1-1 常見排序算法二、內(nèi)排序相關(guān)算法2.1 插入排序核心思想：將一個待排序的數(shù)據(jù)元素插入

2、到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)據(jù)元素依然有序，直到待排序數(shù)據(jù)元素全部插入完為止。2.1.1 直接插入排序核心思想：將欲插入的第i個數(shù)據(jù)元素的關(guān)鍵碼與前面已經(jīng)排序好的i-1、i-2 、i-3、 數(shù)據(jù)元素的值進行順序比較，通過這種線性搜索的方法找到第i個數(shù)據(jù)元素的插入位置 ，并且原來位置 的數(shù)據(jù)元素順序后移，直到全部排好順序。直接插入排序中，關(guān)鍵詞相同的數(shù)據(jù)元素將保持原有位置不變，所以該算法是穩(wěn)定的，時間復(fù)雜度的最壞值為平方階O(n2)，空間復(fù)雜度為常數(shù)階O(l)。Python源代碼：1. #-直接插入排序- 2. def insert_sort(data_list)

3、: 3.  #遍歷數(shù)組中的所有元素，其中0號索引元素默認已排序，因此從1開始 4.  for x in range(1, len(data_list): 5.  #將該元素與已排序好的前序數(shù)組依次比較，如果該元素小，則交換 6.  #range(x-1,-1,-1):從x-1倒序循環(huán)到0 7.  for i in range(x-1, -1, -1): 8.  #判斷：如果符合條件則交換

4、 9.  if data_listi > data_listi+1: 10.  temp = data_listi+1 11.  data_listi+1 = data_listi 12.  data_listi = temp 2.1.2 希爾排序核心思想：是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序;隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。

5、希爾排序時間復(fù)雜度會比O(n2)好一些，然而，多次插入排序中，第一次插入排序是穩(wěn)定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，所以希爾排序是不穩(wěn)定的。Python源代碼：1. #-希爾排序- 2. def insert_shell(data_list): 3.  #初始化step值，此處利用序列長度的一半為其賦值 4.  group = int(len(data_list)/2) 5.  #第一層循環(huán)：依次改變group值對列表進行分組 6.  whi

6、le group > 0: 7.  #下面：利用直接插入排序的思想對分組數(shù)據(jù)進行排序 8.  #range(group,len(data_list):從group開始 9.  for i in range(group, len(data_list): 10.  #range(x-group,-1,-group):從x-group開始與選定元素開始倒序比較，每個比較元素之間間隔group 11.  for j&#

7、160;in range(i-group, -1, -group): 12.  #如果該組當(dāng)中兩個元素滿足交換條件，則進行交換 13.  if data_listj > data_listj+group: 14.  temp = data_listj+group 15.  data_listj+group = data_listj 16.  data_listj = te

8、mp 17.  #while循環(huán)條件折半 18.  group = int(group / 2) 2.2 選擇排序核心思想：每一趟掃描時，從待排序的數(shù)據(jù)元素中選出關(guān)鍵碼最小或最大的一個元素，順序放在已經(jīng)排好順序序列的最后，直到全部待排序的數(shù)據(jù)元素排完為止。2.2.1 直接選擇排序核心思想：給每個位置選擇關(guān)鍵碼最小的數(shù)據(jù)元素，即：選擇最小的元素與第一個位置的元素交換，然后在剩下的元素中再選擇最小的與第二個位置的元素交換，直到倒數(shù)第二個元素和最后一個元素比較為止。根據(jù)其基本思想，每當(dāng)掃描一趟時，如果當(dāng)前元素比

9、一個元素小，而且這個小元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，則它們的位置發(fā)生了交換，所以直接選擇排序時不穩(wěn)定的，其時間復(fù)雜度為平方階O(n2)，空間復(fù)雜度為O(l)。Python源代碼：1. #-直接選擇排序- 2. def select_sort(data_list): 3. #依次遍歷序列中的每一個元素 4.  for i in range(0, len(data_list): 5. #將當(dāng)前位置的元素定義此輪循環(huán)當(dāng)中的最小值 6.  minimum =&#

10、160;data_listi 7. #將該元素與剩下的元素依次比較尋找最小元素 8.  for j in range(i+1, len(data_list): 9.  if data_listj < minimum: 10.  temp = data_listj; 11.  data_listj = minimum; 12.  minimum = te

11、mp 13. #將比較后得到的真正的最小值賦值給當(dāng)前位置 14.  data_listi = minimum 2.2.2 堆排序堆排序時對直接選擇排序的一種有效改進。核心思想：將所有的數(shù)據(jù)建成一個堆，最大的數(shù)據(jù)在堆頂，然后將堆頂?shù)臄?shù)據(jù)元素和序列的最后一個元素交換;接著重建堆、交換數(shù)據(jù)，依次下去，從而實現(xiàn)對所有的數(shù)據(jù)元素的排序。完成堆排序需要執(zhí)行兩個動作：建堆和堆的調(diào)整，如此反復(fù)進行。堆排序有可能會使得兩個相同值的元素位置發(fā)生互換，所以是不穩(wěn)定的，其平均時間復(fù)雜度為0(nlog2n)，空間復(fù)雜度為O(l)。Python源代碼：1. #-

12、堆排序- 2. #*獲取左右葉子節(jié)點* 3. def LEFT(i): 4.  return 2*i + 1 5.   6. def RIGHT(i): 7.  return 2*i + 2 8.   9. #* 調(diào)整大頂堆 * 10. #data_list:待調(diào)整序列 length: 序列長度 i:需要調(diào)整的結(jié)點 11. de

13、f adjust_max_heap(data_list,length,i): 12. #定義一個int值保存當(dāng)前序列最大值的下標(biāo) 13.  largest = i 14. #執(zhí)行循環(huán)操作：兩個任務(wù)：1 尋找最大值的下標(biāo)；2.最大值與父節(jié)點交換 15.  while 1: 16. #獲得序列左右葉子節(jié)點的下標(biāo) 17.  left, right = LEFT(i), RIGHT(i) 18. #當(dāng)左葉子節(jié)點的下

14、標(biāo)小于序列長度 并且 左葉子節(jié)點的值大于父節(jié)點時，將左葉子節(jié)點的下標(biāo)賦值給largest 19.  if (left < length) and (data_listleft > data_listi): 20.  largest = left 21.  #print('左葉子節(jié)點') 22.  else: 23.  largest = i

15、 24. #當(dāng)右葉子節(jié)點的下標(biāo)小于序列長度 并且 右葉子節(jié)點的值大于父節(jié)點時，將右葉子節(jié)點的下標(biāo)值賦值給largest 25.  if (right < length) and (data_listright > data_listlargest): 26.  largest = right 27.  #print('右葉子節(jié)點') 28. #如果largest不等于i 

16、;說明當(dāng)前的父節(jié)點不是最大值，需要交換值 29.  if (largest != i): 30.  temp = data_listi 31.  data_listi = data_listlargest 32.  data_listlargest = temp 33.  i = largest 34.  #print(largest) 35.  

17、continue 36.  else: 37.  break 38.   39. #* 建立大頂堆 * 40. def build_max_heap(data_list): 41.  length = len(data_list) 42.  for x in range(int(length-1)/2),-1,-1): 43.  adjust_max_heap(data_lis

18、t,length,x) 44.   45. #* 堆排序 * 46. def heap_sort(data_list): 47. #先建立大頂堆，保證最大值位于根節(jié)點；并且父節(jié)點的值大于葉子結(jié)點 48.  build_max_heap(data_list) 49. #i：當(dāng)前堆中序列的長度.初始化為序列的長度 50.  i = len(data_list) 51. #執(zhí)行循環(huán)：1. 每次取出堆頂元素置于序列的最后(len-1,

19、len-2,len-3.) 52. # 2. 調(diào)整堆，使其繼續(xù)滿足大頂堆的性質(zhì)，注意實時修改堆中序列的長度 53.  while i > 0: 54.  temp = data_listi-1 55.  data_listi-1 = data_list0 56.  data_list0 = temp 57. #堆中序列長度減1 58.  i =

20、0;i-1 59. #調(diào)整大頂堆 60.  adjust_max_heap(data_list, i, 0) 2.3交換排序核心思想：顧名思義，就是一組待排序的數(shù)據(jù)元素中，按照位置的先后順序相互比較各自的關(guān)鍵碼，如果是逆序，則交換這兩個數(shù)據(jù)元素，直到該序列數(shù)據(jù)元素有序為止。2.3.1 冒泡排序核心思想：對于待排序的一組數(shù)據(jù)元素，把每個數(shù)據(jù)元素看作有重量的氣泡，按照輕氣泡不能在重氣泡之下的原則，將未排好順序的全部元素自上而下的對相鄰兩個元素依次進行比較和調(diào)整，讓較重的元素往下沉，較輕的往上冒。根據(jù)基本思想，只有在兩個元素的順序與排序要求

21、相反時才將調(diào)換它們的位置，否則保持不變，所以冒泡排序時穩(wěn)定的。時間復(fù)雜度為平方階O(n2)，空間復(fù)雜度為O(l)。Python源代碼：1. #-冒泡排序- 2. def bubble_sort(data_list): 3.  length = len(data_list) 4. #序列長度為length，需要執(zhí)行l(wèi)ength-1輪交換 5.  for x in range(1,length): 6. #對于每一輪交換，都將序列當(dāng)中的左右元素進行比較 7.

22、#每輪交換當(dāng)中，由于序列最后的元素一定是最大的，因此每輪循環(huán)到序列未排序的位置即可 8.  for i in range(0,length-x): 9.  if data_listi > data_listi+1: 10.  temp = data_listi 11.  data_listi = data_listi+1 12.  data_listi+1 = temp&

23、#160;2.3.2 快速排序快速排序是對冒泡排序本質(zhì)上的改進。核心思想：是一個就地排序，分而治之，大規(guī)模遞歸的算法。即：通過一趟掃描后確?；鶞?zhǔn)點的這個數(shù)據(jù)元素的左邊元素都比它小、右邊元素都比它大，接著又以遞歸方法處理左右兩邊的元素，直到基準(zhǔn)點的左右只有一個元素為止?？焖倥判驎r一個不穩(wěn)定的算法，其最壞值的時間復(fù)雜度為平方階O(n2)，空間復(fù)雜度為O(log2n)。Python源代碼：1. #-快速排序- 2. #data_list：待排序的序列；start排序的開始index,end序列末尾的index 3. #對于長度為length的序列：start =

24、0;0;end = length-1 4. def quick_sort(data_list,start,end): 5.  if start < end: 6.  i , j , pivot = start, end, data_liststart 7.  while i < j: 8. #從右開始向左尋找第一個小于pivot的值&#

25、160;9.  while (i < j) and (data_listj >= pivot): 10.  j = j-1 11. #將小于pivot的值移到左邊 12.  if (i < j): 13.  data_listi = data_listj 14.  i = i+1 15. #從左開始向右尋找第一

26、個大于pivot的值 16.  while (i < j) and (data_listi < pivot): 17.  i = i+1 18. #將大于pivot的值移到右邊 19.  if (i < j): 20.  data_listj = data_listi 21.  j = j-1 22.

27、 #循環(huán)結(jié)束后，說明 i=j，此時左邊的值全都小于pivot,右邊的值全都大于pivot 23. #pivot的位置移動正確，那么此時只需對左右兩側(cè)的序列調(diào)用此函數(shù)進一步排序即可 24. #遞歸調(diào)用函數(shù)：依次對左側(cè)序列：從0  i-1/右側(cè)序列：從i+1  end 25.  data_listi = pivot 26. #左側(cè)序列繼續(xù)排序 27.  quick_sort(data_list,start,i-1) 28. #右側(cè)序列繼續(xù)排序

28、0;29.  quick_sort(data_list,i+1,end) 2.4歸并排序核心思想：把數(shù)據(jù)序列遞歸地分成短序列，即把1分成2、2分成4、依次分解，當(dāng)分解到只有1個一組的時候排序這些分組，然后依次合并回原來的序列，不斷合并直到原序列全部排好順序。合并過程中可以確保兩個相等的當(dāng)前元素中，把處在前面的元素保存在結(jié)果序列的前面，因此歸并排序是穩(wěn)定的，其時間復(fù)雜度為O(nlog2n)，空間復(fù)雜度為O(n)。Python源代碼：1. #-歸并排序- 2. #這是合并的函數(shù) 3. # 將序列data_listfirst.mid與序列data_l

29、istmid+1.last進行合并 4. def mergearray(data_list,first,mid,last,temp): 5. #對i,j,k分別進行賦值 6.  i,j,k = first,mid+1,0 7. #當(dāng)左右兩邊都有數(shù)時進行比較，取較小的數(shù) 8.  while (i <= mid) and (j <= last): 9.  if data_listi

30、0;<= data_listj: 10.  tempk = data_listi 11.  i = i+1 12.  k = k+1 13.  else: 14.  tempk = data_listj 15.  j = j+1 16.  k = k+1 17. #如果左邊序列還有數(shù) 18.  

31、;while (i <= mid): 19.  tempk = data_listi 20.  i = i+1 21.  k = k+1 22. #如果右邊序列還有數(shù) 23.  while (j <= last): 24.  tempk = data_listj 25.  j = j+1 

32、;26.  k = k+1 27. #將temp當(dāng)中該段有序元素賦值給data_list待排序列使之部分有序 28.  for x in range(0,k): 29.  data_listfirst+x = tempx 30. # 這是分組的函數(shù) 31. def merge_sort(data_list,first,last,temp): 32.  if first < 

33、;last: 33.  mid = (int)(first + last) / 2) 34. #使左邊序列有序 35.  merge_sort(data_list,first,mid,temp) 36. #使右邊序列有序 37.  merge_sort(data_list,mid+1,last,temp) 38. #將兩個有序序列合并 39.  mergearray(data_list,first,mid,last,temp)

34、 40. # 歸并排序的函數(shù) 41. def merge_sort_array(data_list): 42. #聲明一個長度為len(data_list)的空列表 43.  temp = len(data_list)*None 44. #調(diào)用歸并排序 45.  merge_sort(data_list,0,len(data_list)-1,temp) 2.5 基數(shù)排序核心思想：首先是低位排序，然后收集;其次是高位排序，然后再收集;依次類推，直到最高位。Python

35、源代碼：1. #-基數(shù)排序- 2. #確定排序的次數(shù) 3. #排序的順序跟序列中最大數(shù)的位數(shù)相關(guān) 4. def radix_sort_nums(data_list): 5.  maxNum = data_list0 6. #尋找序列中的最大數(shù) 7.  for x in data_list: 8.  if maxNum < x: 9.  maxNum = x

36、60;10. #確定序列中的最大元素的位數(shù) 11.  times = 0 12.  while (maxNum > 0): 13.  maxNum = (int)(maxNum/10) 14.  times = times+1 15.  return times 16. #找到num從低到高第pos位的數(shù)據(jù) 17. def get_num_pos(num,pos

37、): 18.  return (int)(num/(10*(pos-1)%10 19. #基數(shù)排序 20. def radix_sort(data_list): 21.  count = 10*None #存放各個桶的數(shù)據(jù)統(tǒng)計個數(shù) 22.  bucket = len(data_list)*None #暫時存放排序結(jié)果 23. #從低位到高位依次執(zhí)行循環(huán) 24.  for pos in&#

38、160;range(1,radix_sort_nums(data_list)+1): 25.  #置空各個桶的數(shù)據(jù)統(tǒng)計 26.  for x in range(0,10): 27.  countx = 0 28.  #統(tǒng)計當(dāng)前該位(個位，十位，百位.)的元素數(shù)目 29.  for x in range(0,len(data_list): 30.  #統(tǒng)計各個桶將要裝進去的元素個數(shù) 31.  j = get_num_pos(int(data_listx),pos) 32.  countj = countj+1 33.