快速排序 - quick sort python

快速排序是最常用的一种排序，因为它可以取得比较好的平均性能。快速排序是一种递归算法。采用了分而治之的思想。
它的核心步骤是：
1. 把一个序列分成左右两个部分，要求左边的数都比分界点小或相等，右边的数都比分界点的数大。
2. 对步骤1分出来的左右两个部分同样执行1到2的步骤。

那么如何把一个序列分成两个部分呢？设定两个指针i和j，还要设定一个初始比较值x。可以取序列最后的值为x。i左边的都比x小。j是迭代指针，从序列开头到倒数第二个数开始迭代：
1. 如果j指向的值比x大，j下移一位，i不动
2. 如果j指向的值比x小，把i下移一位，再把i和j指向的值交换。然后j下移一位
3. 最后把最后的值和i+1的值交换。

也就是逐步的将比x小的值加到i的队列中来

引用

# python quick sort
def exchange(i, j):
    x = array[i]
    array[i]=array[j]
    array[j]=x
   
def partition(p,r):
    x=array[r]
    i=p-1
    for j in range(p,r-1,1):
        if array[j]<x:
            i=i+1
            exchange(i, j)
    exchange(r,i+1)
    return i+1

def quickSort(p,r):
    if p<r:
        x=partition(p,r)
        quickSort(p,x-1)
        quickSort(x+1,r)

array=[2,5,3,10,8]
quickSort(0,4)
print array

评论

3 楼 JackyCheng2007 2011-02-19  

列表的过滤与映射：

[mapping-expression for element in source-list if filter-expression]

Python 的强大特性之一是其对 list 的解析, 它提供一种紧凑的方法, 可以通过对 list 中的每个元素应用一个函数, 从而将一个 list 映射为另一个 list。

过滤器表达式可以是返回值为真或者假（在 Python 中是 几乎任何东西）的任何表达式。任何经过滤器表达式演算值为元素的真都可以包含在映射中。其它的元素都将忽略，它们不会进入映射表达式，更不会包含在输出列表中。

2 楼 JackyCheng2007 2010-12-01  

感谢高手d指点，受益匪浅，学习了

1 楼 simbas 2010-11-26  

def qsort(L):
    if 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]])

print qsort([2,5,3,10,8])