Python常见排序算法实现与测速源码,python测速,Python常见排序算法
Python常见排序算法实现与测速源码,python测速,Python常见排序算法
Python常见排序算法实现与测速,是Python算法相关,测试排序方法看看哪个Python排序方法的执行速度最快。本文为大家提供了用Python来实现各种排序算法的性能测试的源码详解与下载。
好的排序算法,不但是要准确计算出结果,更要在保证结果正确的前提下更加的节省时间。所以来为python常见排序算法做个测速是很有必要的。
源码中需要用到random与time模块方法。
import random import time DEBUG = False N = 1000 # number of elements in listlist1 = [] # list of integer elementsfor i in range(0, N): list1.append(random.randint(0, N-1))def print_timing(func): def wrapper(*arg): t1 = time.clock() res = func(*arg) t2 = time.clock() print '%s took %0.3fms' % (func.func_name, (t2-t1)*1000.0) return res return wrapper@print_timingdef adaptive_merge_sort(list2): """adaptive merge sort, built into Python since version 2.3""" list2.sort()@print_timingdef bubble_sort(list2): swap_test = False for i in range(0, len(list2) - 1): for j in range(0, len(list2) - i - 1): if list2[j] > list2[j + 1]: list2[j], list2[j + 1] = list2[j + 1], list2[j] # swap swap_test = True if swap_test == False: break@print_timingdef selection_sort(list2): for i in range(0, len (list2)): min = i for j in range(i + 1, len(list2)): if list2[j] < list2[min]: min = j list2[i], list2[min] = list2[min], list2[i] @print_timingdef insertion_sort(list2): for i in range(1, len(list2)): save = list2[i] j = i while j > 0 and list2[j - 1] > save: list2[j] = list2[j - 1] j -= 1 list2[j] = save @print_timingdef quick_sort(list2): quick_sort_r(list2, 0, len(list2) - 1)def quick_sort_r(list2 , first, last): if last > first: pivot = partition(list2, first, last) quick_sort_r(list2, first, pivot - 1) quick_sort_r(list2, pivot + 1, last)def partition(list2, first, last): sred = (first + last)/2 if list2[first] > list2 [sred]: list2[first], list2[sred] = list2[sred], list2[first] # swap if list2[first] > list2 [last]: list2[first], list2[last] = list2[last], list2[first] # swap if list2[sred] > list2[last]: list2[sred], list2[last] = list2[last], list2[sred] # swap list2 [sred], list2 [first] = list2[first], list2[sred] # swap pivot = first i = first + 1 j = last while True: while i <= last and list2[i] <= list2[pivot]: i += 1 while j >= first and list2[j] > list2[pivot]: j -= 1 if i >= j: break else: list2[i], list2[j] = list2[j], list2[i] # swap list2[j], list2[pivot] = list2[pivot], list2[j] # swap return j#www.iplaypy.com@print_timingdef heap_sort(list2): first = 0 last = len(list2) - 1 create_heap(list2, first, last) for i in range(last, first, -1): list2[i], list2[first] = list2[first], list2[i] establish_heap_property (list2, first, i - 1)def create_heap(list2, first, last): i = last/2 while i >= first: establish_heap_property(list2, i, last) i -= 1def establish_heap_property(list2, first, last): while 2 * first + 1 <= last: k = 2 * first + 1 if k < last and list2[k] < list2[k + 1]: k += 1 if list2[first] >= list2[k]: break list2[first], list2[k] = list2[k], list2[first] first = k@print_timingdef merge_sort(list2): merge_sort_r(list2, 0, len(list2) -1)def merge_sort_r(list2, first, last): if first < last: sred = (first + last)/2 merge_sort_r(list2, first, sred) merge_sort_r(list2, sred + 1, last) merge(list2, first, last, sred)def merge(list2, first, last, sred): helper_list = [] i = first j = sred + 1 while i <= sred and j <= last: if list2 [i] <= list2 [j]: helper_list.append(list2[i]) i += 1 else: helper_list.append(list2 [j]) j += 1 while i <= sred: helper_list.append(list2[i]) i +=1 while j &l2000t;= last: helper_list.append(list2[j]) j += 1 for k in range(0, last - first + 1): list2[first + k] = helper_list [k]def print10(list2): for k in range(10): print list2[k], printif __name__ == "__main__" : print "timing 7 sorting algorithms with a list of 1000 integers:" list2 = list(list1) adaptive_merge_sort(list2) if DEBUG: print10(list2) list2 = list(list1) bubble_sort(list2) if DEBUG: print10(list2) list2 = list(list1) heap_sort(list2) if DEBUG: print10(list2) list2 = list(list1) insertion_sort(list2) if DEBUG: print10(list2) list2 = list(list1) merge_sort(list2) if DEBUG: print10(list2) list2 = list(list1) quick_sort(list2) if DEBUG: print10(list2) list2 = list(list1) selection_sort(list2) if DEBUG: print10(list2) # final test list2 = list(list1) if DEBUG: print "final test: ", print10(list2)
Python算法相关文章推荐:
1、Python求素数的快速算法源码示例
2、Python组合生成与数量计算的实现方法
3、Python编写的常见排序算法源码
编橙之家文章,
相关内容
- Python统计代码行数的快捷方法,python统计行数,想知道一
- 如何用Python方法获取图片的准确尺寸,,Python如何获取图
- 把Gmail邮件转发到gtalk的Python方法,gtalkpython,用Python方法
- Python取出指定文本中出现频率最大值的方法,python最大
- 如何用Python来计算已经过去的时间,python已经过去,如何
- Python指定目录递归遍历源码示例,python递归,本文是关于
- Python生成0-9任意4位数字组合的方法,python生成0-94位,编
- Python获取Windows窗口标题并输出的脚本方法,python窗口
- 指定地区天气预报查询的Python方法,地区天气预报pyt
- Python识别网站验证码的方法源码,,学习Python教程之前
评论关闭