快速排序练习(一)

为了方便，使用了python作为编程语言，具体实现参考了《编程珠玑》

总结一下快速排序的主要步骤为：

1. 选取一个参考值t

2. 经过一次筛选后，分为小于t，t，和大于t三个区间

3. 对小于t，和大于t两个区间进行递归，完成排序

方法一：单向循环

 1 #!/usr/bin/env python
 2 
 3 import random
 4 
 5 #构造随机列表
 6 a = range(0,10)
 7 random.shuffle(a)
 8 print a
 9 
10 def qsort1(a, l, u):
11     if l >= u:
12         return
13         
14     #选取列表第一个值为参考，以m为分界点，左边小于等于t，右边大于t
15     m = l
16     t = a[l]
17     
18     #向右循环找小于t的值，如果找到m值加一，同时将该值换到m左侧
19     for i in range(l+1, u+1):
20         if a[i] < t:
21             m += 1
22             a[m],a[i] = a[i],a[m]
23     
24     #循环结束，将参考值换到中间位置，完成一次筛选
25     a[l],a[m] = a[m],a[l]
26     
27     #分别递归，l~m-1和m+1~u两个区间
28     qsort1(a, l, m-1)
29     qsort1(a, m+1, u)
30 
31     
32 qsort1(a, 0, len(a)-1)
33 print a

下图表示了循环过程中的状态