http://www.blogjava.net/todayx-org/archive/2012/01/08/368091.html
http://blog.csdn.net/wl044090432/article/details/54668215
一 冒泡排序
// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定
import random from app01.decorator import * @cal_time def bubble(li): for i in range(len(li)-1): for j in range(len(li)-1-i): if li[j]>li[j+1]: li[j],li[j+1]=li[j+1],li[j] print(li) li = list(range(10000)) random.shuffle(li) bubble(li)
decorator.py :专门计算时间的装饰器
import time def cal_time(func): def inner(*args,**kwargs): t1=time.time() res=func(*args,**kwargs) print('耗时:',time.time()-t1) return res return inner
二 插入排序
import random from app01.decorator import * li=list(range(1000)) random.shuffle(li) @cal_time def insert_sort(li): for i in range(1,len(li)): # i 表示无序区第一个数 tmp = li[i] # 摸到的牌 j = i - 1 # j 指向有序区最后位置 while li[j] > tmp and j >= 0: #循环终止条件: 1. li[j] <= tmp; 2. j == -1 li[j+1] = li[j] j -= 1 li[j+1] = tmp print(li) insert_sort(li)
三 选择排序
import random from app01.decorator import * @cal_time def select_sort(li): for i in range(len(li)): # i 表示趟数,也表示无序区开始的位置 min_loc=i # 最小数的位置 for j in range(i+1,len(li)): if li[j]<li[min_loc]: min_loc=j li[min_loc],li[i]=li[i],li[min_loc] print(li) li=list(range(1000)) random.shuffle(li) select_sort(li)
四 快速排序
http://blog.csdn.net/morewindows/article/details/6684558
import random from app01.decorator import * def _quick_sort(li,left,right): if left<right: mid=partition(li,left,right) _quick_sort(li,left,mid-1) _quick_sort(li,mid+1,right) def partition(li,left,right): tmp=li[left] while left<right: while left<right and li[right] >=tmp: right-=1 li[left]=li[right] while left<right and li[left] <=tmp: left+=1 li[right]=li[left] li[right]=tmp return right @cal_time def quick_sort(li,left,right): _quick_sort(li,left,right) li=list(range(100000)) random.shuffle(li) quick_sort(li,0,len(li)-1)