# timing 7 different Python sorting algorithms with a list of integers
# each function is given the same list (fresh copy each time)
# tested with Python2.7
# -*- coding: utf-8 -*-
"""
Created on Tue Oct 18 09:54:20 2011
@author: Guo
"""
import random # for generating random numbers
import time # for timing each sort function with time.clock()
DEBUG = False # set True to check results of each sort
N = 1000 # number of elements in list
list1 = [] # list of integer elements
for i in range(0, N):
list1.append(random.randint(0, N-1))
#print list1 # test
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
# declare the @ decorator just above each sort function, invokes print_timing()
@print_timing
def adaptive_merge_sort(list2):
"""adaptive merge sort, built into Python since version 2.3"""
list2.sort()
@print_timing
def bubble_sort(list2):
#swap_test = False
for i in range(0, len(list2) - 1):
# as suggested by kubrick, makes sense
swap_test = False
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
# selection sort
@print_timing
def 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] # swap
# insertion sort
@print_timing
def 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
# quick sort
@print_timing
def quick_sort(list2):
quick_sort_r(list2, 0, len(list2) - 1)
# quick_sort_r, recursive (used by quick_sort)
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)
# partition (used by quick_sort_r)
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
# heap sort
@print_timing
def 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] # swap
establish_heap_property (list2, first, i - 1)
# create heap (used by heap_sort)
def create_heap(list2, first, last):
i = last/2
while i >= first:
establish_heap_property(list2, i, last)
i -= 1
# establish heap property (used by create_heap)
def 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] # swap
first = k
# merge sort
@print_timing
def merge_sort(list2):
merge_sort_r(list2, 0, len(list2) -1)
# merge sort recursive (used by merge_sort)
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)
# merge (used by merge_sort_r)
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 <= last:
helper_list.append(list2[j])
j += 1
for k in range(0, last - first + 1):
list2[first + k] = helper_list [k]
# test sorted list by printing the first 10 elements
def print10(list2):
for k in range(10):
print list2[k],
print
# run test if script is executed
if __name__ == "__main__" :
print "timing 7 sorting algorithms with a list of 1000 integers:"
# make a true copy of list1 each time
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)
#raw_input( "Press Enter to continue..." )
"""
typical results:
timing 7 sorting algorithms with a list of 1000 integers:
adaptive_merge_sort took 0.560ms
bubble_sort took 269.691ms
heap_sort took 13.556ms
insertion_sort took 130.870ms
merge_sort took 19.272ms
quick_sort took 6.849ms
selection_sort took 120.291ms
`````````````````````````````
timing 7 sorting algorithms with a list of 1000 integers:
adaptive_merge_sort took 0.470ms
bubble_sort took 242.426ms
heap_sort took 10.453ms
insertion_sort took 112.837ms
merge_sort took 11.294ms
quick_sort took 6.688ms
selection_sort took 124.995ms
"""
分享到:
相关推荐
菜鸟一枚,编程初学者,最近想使用Python3实现几个简单的机器学习分析方法,记录一下自己的学习过程。 关于KMeans算法本身就不做介绍了,下面记录一下自己遇到的问题。 一 、关于初始聚类中心的选取 初始聚类中心的...
蛙跳算法python代码
python flask实时播放算法处理后的实时视频流。详情:https://blog.csdn.net/qq_34717531/article/details/125079685?spm=1001.2014.3001.5502。 本代码实现python,flask部署web端,可输入图片,视频,RTSP数据流。...
AUST-空测-17朱叨叨同学的水准网平差程序(间接平差原理,全部...欢迎各位同行下载,运行有问题可以在CSDN上私聊我,由于是编程菜鸟,程序书写和标注可能不是很规范,算法很多地方也不够精简,所以欢迎批评指正的意见!
网络爬虫:通过Python实现新浪新闻的爬取,可爬取新闻页面上的标题、文本、图片、视频链接(保留排版) 推荐算法:权重衰减+标签推荐+区域推荐+热点推荐 权重衰减进行用户兴趣标签权重的衰减,避免内容推荐的过度...
除矩阵运算、绘制函数、数据图像等常用功能外,MATLAB还可用来创建用户界面,以及调用其它语言包括C、C++、Java、Python编写的程序。MATLAB主要用于数值运算,但利用为数众多的附加工具箱,它也适合不同领域的应用,...
01.01 2.x与3.x版本区别.png 02 基础语法.png 02.01 命令行参数.png 03 基本数据类型.png 03.01 数据类型转换 int() 函数.png 03.02 数据类型转换 float() 函数.png 03.03 数据类型转换 complex() 函数.png ...
python人工智能 pythonNLP python高阶 python算法工程师 chatgpt
python-noob 简单的学生管理示例 你会学什么 清单 印刷价值 类 直接从班级打印 搜索算法 从列表中删除值 等等.. 特征 列出该死的学生 :school: 添加新学生 :ewe: :Japanese_symbol_for_beginner: 删除顽皮的 :...
通过简短的小实例,系统学习python,所介绍实例不能涵盖所有python内容,但每一个都是极为实用,包括基础、绘图、数据分析、算法等,涵盖内容较广泛,实用价值高,实战价值高。
Python 语言简单针对深度学习的算法,以及独特的深度学习框架,将在人工智能领域编程语言中占重要地位。 Python 是一种代表简单主义思想的语言。吉多·罗萨姆对 Python 的定位是“优雅,明确,简单”。Python 拒绝了...
leetcode-python- python基础巩固以及leetcode刷题代码 菜鸟学习日记 在leetcode上面刷的一些算法题,还有一些Python基础语法的复习,持续更新。。。 1. 2. 3. #失效 4. 5. 6. 7. 8. 9. #失效 10. 11. 12. 13. 14. ...
利用Python+Gurobi编写代码,复现文章:Solving two-stage robust optimization problems using a column-and- constraint generation method。
内容来源:廖雪峰的官方教程/菜鸟教程/ CSDN / github /《流畅的Python》 :变量/字符串/数字和运算符 :列表/元组 :字典/套 :如果/循环 :调用函数/定义函数/函数的参数 :/列表生成式/生成器/迭代器 :高...
部分算法题解 C++
leetcode算法python版,包括算法的答案,数百道题。提升算法 必备
python希尔排序,开源: https://codechina.csdn.net/-/snippets/353 基于菜鸟的https://www.runoob.com/python3/python-shellsort.html
本资源是:Python从零基础到大牛项目实战:抓取景点评论数量+旅游景点推荐。...本项目是完整的开发实战项目,实现景点评论的抓取以及实现旅游景点的推荐算法。 适合Python开发者和学习Python的爱好者。
本文实例讲述了Python实现的线性回归算法。分享给大家供大家参考,具体如下: 用python实现线性回归 Using Python to Implement Line Regression Algorithm 小菜鸟记录学习过程 代码: #encoding:utf-8 Author: ...