Python实现的几种排序算法

电玩女神 2022-09-18 10:56 304阅读 0赞

FuniK

Python实现的几种排序算法

FuniK 发布于 2013年10月11日 15时, 6评/489阅

分享到

新浪微博 腾讯微博

收藏 +8

踩 顶 0

包括了：冒泡排序，插入排序，选择排序，快速排序和希尔排序
Python版本：2.7.3

标签： <无>

代码片段(1)**[全屏查看所有代码]

1. [文件] sort.py ~ 2KB 下载(30) 跳至 [1] [全屏预览]

view source print ?








001 import sys, getopt, random







002  







003 def bubble_sort(seq):







004     for i in range(len(seq)):







005         for j in range(1,len(seq)):







006             if seq[j-1]>seq[j]:







007                 seq[j-1], seq[j]= seq[j], seq[j-1]







008     return seq







009  







010 def insertion_sort(seq):







011     for i in range(1,len(seq)):







012         tmp=seq[i]







013         pos=i;







014         for j in range(i-1,-1,-1):







015             if seq[j]>tmp:







016                 seq[j+1]=seq[j]







017                 pos=j







018         seq[pos]=tmp







019     return seq







020  







021 def selection_sort(seq):







022     for i in range(len(seq)):







023         min_index=i;







024         for j in range(i,len(seq)):







025             if seq[j]<seq[min_index]:







026                 min_index=j







027         seq[i],seq[min_index]=seq[min_index],seq[i]







028     return seq







029  







030 def partition(seq,p,l,r):







031     pivot = seq[p]







032     seq[p],seq[r]=seq[r],seq[p]







033     p_pos = l







034     for i in range(l,r):







035         if seq[i]<=pivot:







036             seq[i],seq[p_pos]=seq[p_pos],seq[i]







037             p_pos=p_pos+1







038     seq[p_pos],seq[r]=seq[r],seq[p_pos]







039     return p_pos







040  







041  







042 def quick_sort(seq,left,right):







043     if left < right:







044         pivot = random.randint(left,right)         







045         mid = partition(seq,pivot,left,right)







046         quick_sort(seq,left,mid-1)







047         quick_sort(seq,mid+1,right)







048     return seq







049  







050 def shell_sort(seq):







051     incr = len(seq)/2







052     while(incr>=1):







053         for i in range(incr,len(seq)):







054             tmp=seq[i]







055             pos=i;







056             for j in range(i-incr,-1,-incr):







057                 if seq[j]>tmp:







058                     seq[j+incr]=seq[j]







059                     pos=j







060             seq[pos]=tmp







061         incr = incr/2  







062     return seq







063  







064 def usage():







065     print ‘Usage: python sort.py sorttype[-q|-i|-b|-s|—shell] sequence’







066     print ‘Example: python sort.py -q 11,32,3,24,5’







067  







068 def main():







069     try:







070         if(len(sys.argv)==1) or (len(sys.argv)!=3):







071             raise Exception()







072         else:







073             opts,args=getopt.getopt(sys.argv[1:],‘qibs’,[‘shell’])







074  







075             if len(args)>0:







076                 seq=[]







077                 tmp=args[0].split(‘,’)







078                 for i in tmp:







079                     seq.append(int(i))







080             else:







081                 raise Exception()







082  







083             for opt in opts:







084                 if opt[0] ==‘-q’:







085                     print quick_sort(seq,0,len(seq)-1)                     







086                 elif opt[0] ==‘-i’:







087                     print insertion_sort(seq)







088                 elif opt[0] ==‘-b’:







089                     print bubble_sort(seq)







090                 elif opt[0] ==‘-s’:







091                     print selection_sort(seq)







092                 elif opt[0] ==‘—shell’:







093                     print shell_sort(seq)                                                          







094  







095     except Exception,e:







096         usage()







097         print e







098         sys.exit()







099  







100 if name ==“main“:







101     main()

发表评论

表情：
评论列表 （有 0 条评论，304人围观）

还没有评论，来说两句吧...

相关阅读