Python八大常見排序算法定義、實現(xiàn)及時間消耗效率分析

本文實例講述了Python八大常見排序算法定義、實現(xiàn)及時間消耗效率分析。分享給大家供大家參考，具體如下：

昨晚上開始總結(jié)了一下常見的幾種排序算法，由于之前我已經(jīng)寫了好幾篇排序的算法的相關(guān)博文了現(xiàn)在總結(jié)一下的話可以說是很方便的，這里的目的是為了更加完整詳盡的總結(jié)一下這些排序算法，為了復(fù)習(xí)基礎(chǔ)的東西，從冒泡排序、直接插入排序、選擇排序、歸并排序、希爾排序、桶排序、堆排序?？焖倥判蛉胧謥矸治龊蛯崿F(xiàn)，在最后也給出來了簡單的時間統(tǒng)計，重在原理、算法基礎(chǔ)，其他的次之，這些東西的熟練掌握不算是對之后的工作或者接下來的準(zhǔn)備面試都是很有幫助的，算法重在理解內(nèi)在含義和理論基礎(chǔ)，在實現(xiàn)的時候才能避開陷阱少出錯誤，這不是說練習(xí)的時候有錯誤不好而是說，有些不該出現(xiàn)的錯誤盡量還是少出現(xiàn)的好，畢竟好的編程習(xí)慣是離不開嚴(yán)格的約束的，好了，這里就不多說了，復(fù)習(xí)一下基礎(chǔ)知識，共同學(xué)習(xí)吧，下面是具體實現(xiàn)，注釋應(yīng)該都很詳細(xì)，就不解釋了：

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
import time
import random
time_dict={}
def time_deco(sort_func):
  '''''
  時間計算的裝飾器函數(shù),可用于計算函數(shù)執(zhí)行時間
  '''
  def wrapper(num_list):
    start_time=time.time()
    res=sort_func(num_list)
    end_time=time.time()
    time_dict[str(sort_func)]=(end_time-start_time)*1000
    print '耗時為：',(end_time-start_time)*1000
    print '結(jié)果為：', res
  return wrapper
def random_nums_generator(max_value=1000, total_nums=20):
  '''''
  隨機(jī)數(shù)列表生成器
  一些常用函數(shù)：
  random隨機(jī)數(shù)生成
  random.random()用于生成一個0到1之間的隨機(jī)數(shù):0 <= n < 1.0；
  random.uniform(a, b)，用于生成一個指定范圍內(nèi)的隨機(jī)符點數(shù)，兩個參數(shù)其中一個是上限，一個是下限。min(a,b) <= n <= max(a,b)；
  randdom.randint(a, b), 用于生成一個指定范圍內(nèi)的整數(shù)，其中a是下限，b是上限： a<= n <= b；
  random.randrange(start, stop, step), 從指定范圍內(nèi)，按指定基數(shù)遞增的集合獲取一個隨機(jī)數(shù)；
  random.choice(sequence), 從序列中獲取一個隨機(jī)元素；
  random.shuffle(x), 用于將一個列表中的元素打亂；
  random.sample(sequence, k), 從指定序列中隨機(jī)獲取指定長度的片斷；
  '''
  num_list=[]
  for i in range(total_nums):
    num_list.append(random.randint(0,max_value))
  return num_list
#@time_deco
def Bubble_sort(num_list):
  '''''
  冒泡排序，時間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)，是穩(wěn)定排序
  '''
  for i in range(len(num_list)):
    for j in range(i,len(num_list)):
      if num_list[i]>num_list[j]: #這里是升序排序
        num_list[i], num_list[j]=num_list[j], num_list[i]
  return num_list
#@time_deco
def Insert_sort(num_list):
  '''''
  直接插入排序，時間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)，是穩(wěn)定排序
  '''
  for i in range(len(num_list)):
    for j in range(0,i):
      if num_list[i]<num_list[j]: #這里是升序排序,跟冒泡排序差別在于，冒泡是向后遍歷，這個是向前遍歷
        num_list[i], num_list[j]=num_list[j], num_list[i]
  return num_list
#@time_deco
def Select_sort(num_list):
  '''''
  選擇排序，時間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)，不是穩(wěn)定排序
  '''
  for i in range(len(num_list)):
    min_value_index=i
    for j in range(i, len(num_list)):
      if num_list[j]<num_list[min_value_index]:
        min_value_index=j #乍一看，感覺冒泡，選擇，插入都很像，選擇跟冒泡的區(qū)別在于：冒泡是發(fā)現(xiàn)大
                 #小數(shù)目順序不對就交換，而選擇排序是一輪遍歷結(jié)束后選出最小值才交換，效率更高
    num_list[i], num_list[min_value_index]=num_list[min_value_index], num_list[i]
  return num_list
#@time_deco
def Merge_sort(num_list):
  '''''
  歸并排序，時間復(fù)雜度O(nlog?n)，空間復(fù)雜度：O(1)，是穩(wěn)定排序
  '''
  if len(num_list)==1:
    return num_list
  length=len(num_list)/2
  list1=num_list[:length]
  list2=num_list[length:]
  result_list=[]
  while len(list1) and len(list2):
    if list1[0]<=list2[0]:
      result_list.append(list1[0])
      del list1[0] #這里需要刪除列表中已經(jīng)被加入到加過列表中的元素，否則最后比較完后列表
    else:       #中剩余元素?zé)o法添加
      result_list.append(list2[0])
      del list1[0]
  if len(list1): #遍歷比較完畢后列表中剩余元素的添加
    result_list+=list1
  else:
    result_list+=list2
  return result_list
#@time_deco
def Shell_sort(num_list):
  '''''
  希爾排序，時間復(fù)雜度：O(n)，空間復(fù)雜度：O(n^2),不是穩(wěn)定排序算法
  '''
  new_list = []
  for one_num in num_list:
    new_list.append(one_num)
  count=len(new_list)
  step=count/2;
  while step>0:
    i=0
    while i<count:
      j=i+step
      while j<count:
        t=new_list.pop(j)
        k=j-step
        while k>=0:
          if t>=new_list[k]:
            new_list.insert(k+1, t)
            break
          k=k-step
        if k<0:
          new_list.insert(0, t)
        #print '---------本輪結(jié)果為：--------'
        #print new_list
        j=j+step
        #print j
      i=i+1
      #print i
    step=step/2   #希爾排序是一個更新步長的算法
  return new_list
#@time_deco
def Tong_sort(num_list):
  '''''
  桶排序，時間復(fù)雜度O(1)，空間復(fù)雜度與最大數(shù)字有關(guān)，可以認(rèn)為是O(n)，典型的空間換時間的做法
  '''
  original_list = []
  total_num=max(num_list) #獲取桶的個數(shù)
  for i in range(total_num+1): #要注意這里需要的數(shù)組元素個數(shù)總數(shù)比total_num數(shù)多一個因為下標(biāo)從0開始
    original_list.append(0)
  for num in num_list:
    original_list[num] += 1
  result_list = []
  for j in range(len(original_list)):
    if original_list[j] != 0:
      for h in range(0,original_list[j]):
        result_list.append(j)
  return result_list
def Quick_sort(num_list):
  '''''
  快速排序，時間復(fù)雜度：O(nlog?n)，空間復(fù)雜度：O(nlog?n)，不是穩(wěn)定排序
  '''
  if len(num_list)<2:
    return num_list
  left_list = [] #存放比基準(zhǔn)結(jié)點小的元素
  right_list = [] #存放比基準(zhǔn)元素大的元素
  base_node = num_list.pop(0) #在這里采用pop()方法的原因就是需要移除這個基準(zhǔn)結(jié)點，并且賦值給base_node這個變量
                #在這里不能使用del()方法，因為刪除之后無法再賦值給其他變量使用，導(dǎo)致最終數(shù)據(jù)缺失
                #快排每輪可以確定一個元素的位置，之后遞歸地對兩邊的元素進(jìn)行排序
  for one_num in num_list:
    if one_num < base_node:
      left_list.append(one_num)
    else:
      right_list.append(one_num)
  return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)
def Heap_adjust(num_list, i, size):
  left_child = 2*i+1
  right_child = 2*i+2
  max_temp = i
  #print left_child, right_child, max_temp
  if left_child<size and num_list[left_child]>num_list[max_temp]:
    max_temp = left_child
  if right_child<size and num_list[right_child]>num_list[max_temp]:
    max_temp = right_child
  if max_temp != i:
    num_list[i], num_list[max_temp] = num_list[max_temp], num_list[i]
    Heap_adjust(num_list, max_temp, size) #避免調(diào)整之后以max為父節(jié)點的子樹不是堆
def Create_heap(num_list, size):
  a = size/2-1
  for i in range(a, -1, -1):
    #print '**********', i
    Heap_adjust(num_list, i, size)
#@time_deco
def Heap_sort(num_list):
  '''''
  堆排序，時間復(fù)雜度：O(nlog?n)，空間復(fù)雜度：O(1)，不是穩(wěn)定排序
  '''
  size=len(num_list)
  Create_heap(num_list, size)
  i = size-1
  while i > 0:
    num_list[0], num_list[i] = num_list[i], num_list[0]
    size -= 1
    i -= 1
    Heap_adjust(num_list, 0, size)
  return num_list
if __name__ == '__main__':
  num_list=random_nums_generator(max_value=100, total_nums=50)
  print 'Bubble_sort', Bubble_sort(num_list)
  print 'Insert_sort', Insert_sort(num_list)
  print 'Select_sort', Select_sort(num_list)
  print 'Merge_sort', Merge_sort(num_list)
  print 'Shell_sort', Shell_sort(num_list)
  print 'Tong_sort', Tong_sort(num_list)
  print 'Heap_sort', Heap_sort(num_list)
  print 'Quick_sort', Quick_sort(num_list)
  # print '-----------------------------------------------------------------------------'
  # for k,v in time_dict.items():
  #   print k, v

結(jié)果如下：

    Bubble_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Insert_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Select_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Merge_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Shell_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Tong_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Heap_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
    Quick_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]

這里沒有使用到裝飾器，主要自己對這個裝飾器不太了解，在快速排序的時候報錯了，也沒有去解決，這里簡單貼一下一個測試樣例使用裝飾器的結(jié)果吧：

    Bubble_sort 耗時為： 0.0290870666504
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Insert_sort 耗時為： 0.0209808349609
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Select_sort 耗時為： 0.0259876251221
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Merge_sort 耗時為： 0.0138282775879
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Shell_sort 耗時為： 0.113964080811
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Tong_sort 耗時為： 0.0460147857666
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Heap_sort 耗時為： 0.046968460083
    結(jié)果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    None
    Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
    -----------------------------------------------------------------------------
    <function Shell_sort at 0x7f8ab9d34410> 0.113964080811
    <function Select_sort at 0x7f8ab9d34230> 0.0259876251221
    <function Insert_sort at 0x7f8ab9d34140> 0.0209808349609
    <function Heap_sort at 0x7f8ab9d34758> 0.046968460083
    <function Merge_sort at 0x7f8ab9d34320> 0.0138282775879
    <function Tong_sort at 0x7f8ab9d34500> 0.0460147857666
    <function Bubble_sort at 0x7f8ab9d34050> 0.0290870666504
接下來有時間的話我想學(xué)一下裝飾器的東西，感覺對于模式化的東西裝飾器簡直就是一個神器，但是得明白會用會寫才行哈！