Python八大常见排序算法定义、实现及时间消耗效率分析

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
import time
import random
time_dict={}
def time_deco(sort_func):
  '''''
  时间计算的装饰器函数,可用于计算函数执行时间
  '''
  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 '结果为：', res
  return wrapper
def random_nums_generator(max_value=1000, total_nums=20):
  '''''
  随机数列表生成器
  一些常用函数：
  random随机数生成
  random.random()用于生成一个0到1之间的随机数:0 <= n < 1.0；
  random.uniform(a, b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。min(a,b) <= n <= max(a,b)；
  randdom.randint(a, b), 用于生成一个指定范围内的整数，其中a是下限，b是上限： a<= n <= b；
  random.randrange(start, stop, step), 从指定范围内，按指定基数递增的集合获取一个随机数；
  random.choice(sequence), 从序列中获取一个随机元素；
  random.shuffle(x), 用于将一个列表中的元素打乱；
  random.sample(sequence, k), 从指定序列中随机获取指定长度的片断；
  '''
  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):
  '''''
  冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
  '''
  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):
  '''''
  直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
  '''
  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):
  '''''
  选择排序，时间复杂度O(n^2)，空间复杂度O(1)，不是稳定排序
  '''
  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 #乍一看，感觉冒泡，选择，插入都很像，选择跟冒泡的区别在于：冒泡是发现大
                 #小数目顺序不对就交换，而选择排序是一轮遍历结束后选出最小值才交换，效率更高
    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):
  '''''
  归并排序，时间复杂度O(nlog"color: #800000">PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：

http://tools.jb51.net/aideddesign/paixu_ys
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。