返回顶部

收藏

Python实现的几种排序算法

更多

包括了:冒泡排序,插入排序,选择排序,快速排序和希尔排序

Python版本:2.7.3

import sys, getopt, random

def bubble_sort(seq):
    for i in range(len(seq)):
        for j in range(1,len(seq)):
            if seq[j-1]>seq[j]:
                seq[j-1], seq[j]= seq[j], seq[j-1]
    return seq

def insertion_sort(seq):
    for i in range(1,len(seq)):
        tmp=seq[i]
        pos=i;
        for j in range(i-1,-1,-1):
            if seq[j]>tmp:
                seq[j+1]=seq[j]
                pos=j
        seq[pos]=tmp
    return seq

def selection_sort(seq):
    for i in range(len(seq)):
        min_index=i;
        for j in range(i,len(seq)):
            if seq[j]<seq[min_index]:
                min_index=j
        seq[i],seq[min_index]=seq[min_index],seq[i]
    return seq

def partition(seq,p,l,r):
    pivot = seq[p]
    seq[p],seq[r]=seq[r],seq[p]
    p_pos = l
    for i in range(l,r):
        if seq[i]<=pivot:
            seq[i],seq[p_pos]=seq[p_pos],seq[i]
            p_pos=p_pos+1
    seq[p_pos],seq[r]=seq[r],seq[p_pos]
    return p_pos

def quick_sort(seq,left,right):
    if left < right: 
        pivot = random.randint(left,right)          
        mid = partition(seq,pivot,left,right)
        quick_sort(seq,left,mid-1)
        quick_sort(seq,mid+1,right)
    return seq

def shell_sort(seq):
    incr = len(seq)/2
    while(incr>=1):
        for i in range(incr,len(seq)):
            tmp=seq[i]
            pos=i;
            for j in range(i-incr,-1,-incr):
                if seq[j]>tmp:
                    seq[j+incr]=seq[j]
                    pos=j
            seq[pos]=tmp
        incr = incr/2  
    return seq

def usage():
    print 'Usage: python sort.py sorttype[-q|-i|-b|-s|--shell] sequence'
    print 'Example: python sort.py -q 11,32,3,24,5'

def main():
    try:
        if(len(sys.argv)==1) or (len(sys.argv)!=3):
            raise Exception()
        else:
            opts,args=getopt.getopt(sys.argv[1:],'qibs',['shell'])

            if len(args)>0:
                seq=[]
                tmp=args[0].split(',')
                for i in tmp:
                    seq.append(int(i))
            else:
                raise Exception()

            for opt in opts:
                if opt[0] =='-q':
                    print quick_sort(seq,0,len(seq)-1)                      
                elif opt[0] =='-i':
                    print insertion_sort(seq)
                elif opt[0] =='-b':
                    print bubble_sort(seq)
                elif opt[0] =='-s':
                    print selection_sort(seq)
                elif opt[0] =='--shell':
                    print shell_sort(seq)                                                           

    except Exception,e:
        usage()
        print e
        sys.exit()

if __name__ =="__main__":
    main()
#该片段来自于http://outofmemory.cn

标签:python,算法

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. fox64194167 发表 2018-05-26 22:31:24 python 找不同 Find the Difference
  2. 老高 发表 2018-08-13 15:41:35 python 堆排序算法
  3. TLHL28 发表 2011-05-23 03:20:37 triple_des(des3) 算法 - php,python 实现
  4. rainy 发表 2015-09-02 15:52:26 网页正文及内容图片提取算法
  5. 数控小V 发表 2016-02-17 03:14:02 机器学习算法 Python&R 速查表
  6. youngsterxyf 发表 2012-11-21 16:00:00 pi的一种并行算法
  7. 姚 广远 发表 2015-06-19 00:23:25 用Python实现各种排序算法
  8. 上官 江 发表 2012-12-02 11:18:18 RC4算法Python实现
  9. 0X55AA 发表 2014-08-12 07:09:15 pyrasite项目总结为一条命令
  10. Yusheng 发表 2016-04-23 19:11:31 字符串匹配算法
  11. 0X55AA 发表 2015-01-05 03:42:41 python的__slots__
  12. 0X55AA 发表 2015-04-29 05:29:52 DHT爬虫站-芭蕉细雨

发表评论