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 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₂n)，空间复杂度：O(1)，是稳定排序 ''' 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]0: i=0 while i<count: j=i+step while j=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 '---------本轮结果为：--------' new_list j i step=step/2 #希尔排序是一个更新步长的算法 return #@time_deco def tong_sort(num_list): ''''' 桶排序，时间复杂度o(1)，空间复杂度与最大数字有关，可以认为是o(n)，典型的空间换时间的做法 ''' original_list=[] total_num=max(num_list) #获取桶的个数 for in range(total_num+1): #要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始 original_list.append(0) num num_list: original_list[num] + result_list range(len(original_list)): if original_list[j] !=0: h range(0,original_list[j]): result_list.append(j) quick_sort(num_list): 快速排序，时间复杂度：o(nlog₂n)，空间复杂度：o(nlog₂n)，不是稳定排序 len(num_list)<2: num_list left_list=[] #存放比基准结点小的元素 right_list=[] #存放比基准元素大的元素 base_node=num_list.pop(0) #在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量 #在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失 #快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序 one_num < base_node: left_list.append(one_num) else: right_list.append(one_num) quick_sort(left_list) [base_node] quick_sort(right_list) heap_adjust(num_list, i, size): left_child=2*i+1 right_child=2*i+2 max_temp left_child, right_child, left_childnum_list[max_temp]: max_temp = left_child if right_childnum_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) #避免调整之后以max为父节点的子树不是堆 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): ''''' 堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序 ''' 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