存档

文章标签 ‘快速排序’

Python排序:快速,冒泡,归并

2011年5月13日 Yarkee 没有评论

之前介绍过qsort,但后来发现稍微有点不妥,终止条件设置成if not L: return L ,有点多余,实际上L长度为1时就可return了,所以改了改终止条件.然后写了下冒泡排序和归并排序,测试了下,运行结果应该没问题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def qsort(L):
    if len(L)<=1: return L
    return qsort([x for x in L[1:] if x<L[0]])+L[0:1]+qsort([x for x in L[1:] if x>=L[0]])
 
def bubblesort(L):
    for i in xrange(0,len(L)):
        for j in xrange(len(L)-1,i,-1):
            if L[j]<L[j-1]:
                L[j-1],L[j]=L[j],L[j-1]
    return L
 
def mergesort(L):
    if len(L)<=1: return L
    left=mergesort(L[0:len(L)/2])
    right=mergesort(L[len(L)/2:len(L)])
    result=[]
    while len(left)>0 or len(right)>0:
        if len(right)<=0 or (len(left)>0 and left[0]<=right[0]):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result

 

分类: 编程 标签: , ,

Python实现快速排序

2011年3月10日 Yarkee 没有评论 

1
2
3
4

def qsort(L):      ＃The argument should be a list
    if not L:return []
    return qsort([x for x in L[1:] if x<L[0]])+L[0:1]+\
	    qsort([x for x in L[1:] if x>=L[0]])

分类: 编程 标签: ,

归并排序与快速排序谁快谁慢

2010年5月14日 Yarkee 4 条评论

用这两种不同的排序方法，分别对1000个无序的数进行排序，看谁更快。当然，也可以把1000替换成10000或者更多（前提是int没有暴掉）。
网上流传着一种快速排序的写法，是用两个指针分别从左至破口大骂和从右至左扫描，那样的代码也太复杂了吧。像下面这段程序写的，要简单得多。

阅读全文…

分类: 编程 标签: ,

WP SlimStat