注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

Python常见排序算法  

2016-07-24 22:42:18|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

常用的时间复杂度为O(n^2)的排序算法有冒泡排序,插入排序和选择排序,时间复杂度为O(nlog2(n))的算法有快速排序,归并排序和堆排序,

这里的快速排序的初始比较值partition是随机给定的,在用python进行编写时能更清楚的理解整个排序算法的过程。

复制代码
  1 import random
  2 def BubbleSort(num):
  3     n=len(num)
  4     for i in range(0,n):
  5         for j in range(i,n):
  6             if num[i]>=num[j]:
  7                 num[i],num[j]=num[j],num[i]
  8     return num
  9 def SelectSort(num):
 10     for i in range(0,len(num)):
 11         mindex=i
 12         for j in range(i,len(num)):
 13             if num[mindex]>num[j]:
 14                 mindex=j
 15         num[mindex],num[i]=num[i],num[mindex]
 16     return num
 17 def InsertSort(num):
 18     for i in range(1,len(num)):
 19         j=i-1
 20         tmp=num[i]
 21         while j>0 and tmp<num[j]:
 22             num[j+1]=num[j]
 23             j-=1
 24         num[j]=tmp
 25     return num
 26 def MergerSort(num):
 27     if len(num)<=1:
 28         return num
 29     left=MergerSort(num[:len(num)/2])
 30     right=MergerSort(num[len(num)/2:])
 31     result=[]
 32     while len(left)>0 and len(right)>0:
 33         if left[0]>right[0]:
 34             result.append(right.pop(0))
 35         else:
 36             result.append(left.pop(0))
 37     if len(left)>0:
 38         result.extend(MergerSort(left))
 39     else:
 40         result.extend(MergerSort(right))
 41     return result
 42 def QuickSort(num):
 43     if len(num)<=1:
 44         return num
 45     greater=[]
 46     less=[]
 47     p=num.pop(random.randint(0,len(num)-1))
 48     for item in num:
 49         if item < p:
 50             less.append(item)
 51         else:
 52             greater.append(item)
 53     return QuickSort(less)+[p]+QuickSort(greater)
 54 ############################################################
 55 def InsertIntoHeap(x,heap):
 56     if len(heap)==0:
 57         heap=[x]
 58         return heap
 59     heap.append(x)
 60     pos=len(heap)
 61     while True:
 62         if pos==1:
 63             return heap
 64         father=pos/2
 65         if heap[father-1]<heap[pos-1]:
 66             heap[father-1],heap[pos-1]=heap[pos-1],heap[father-1]
 67             pos=father
 68         else:
 69             return heap
 70 def CreateHeap(x):
 71     b=[]
 72     for i in x:
 73         InsertIntoHeap(i,b)
 74     return b 
 75 def HandHeap(a):
 76     if a==None or type(a)!=list:
 77         return 
 78     if a==[] or len(a)==1:
 79         return a 
 80     pos=0
 81     while True:
 82         if 2*(pos+1)>len(a):
 83             return a 
 84         if 2*(pos+1)==len(a):
 85             if a[pos]<a[2*pos+1]:
 86                 a[pos],a[2*pos+1]=a[2*pos+1],a[pos]
 87             return a 
 88         if 2*(pos+1)+1<=len(a):
 89             if a[pos]<a[2*pos+1]and a[2*pos+1]>=a[2*pos+2]:  
 90                 a[pos],a[2*pos+1]=a[2*pos+1],a[pos]  
 91                 pos=2*pos+1  
 92             elif a[pos]<a[2*pos+2]and a[2*pos+1]<a[2*pos+2]:  
 93                 a[pos],a[2*pos+2]=a[2*pos+2],a[pos]  
 94                 pos=2*pos+2  
 95             else:  
 96                 return a 
 97 def HeapSort(num):
 98     if num==None or type(num)!=list:
 99         return 
100     b=CreateHeap(num)
101     a=[]
102     while b:
103         a.append(b[0])
104         b[0]=b[len(b)-1]
105         b.pop()
106         b=HandHeap(b)
107     return a
108     
  评论这张
 
阅读(33)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017