By

Contents
  1. 1. 分治法
  2. 2. 左右划分的实现
  3. 3. 递归调用
  4. 4. 性能比较

　　快速排序，算法经典。我这里要做的，就是分析其设计思想并一步步来实现它。

分治法

　　快速排序采用的是“分治法”，其英文名现能体现其特点”divide and conquer”，分割&征服。具体到本算法是这样的：
（以数组从小到大排序为例）

  1. 从数组是选取一个基准数，根据大于或小于该基准数将元素分列到数组左右两端
  2. 对上一步分割出的左右两子数组再次执行步骤1
  3. 循环递归，直到子数组长度为1

　　以上如何体现出“分治”了呢？每操作一次，虽然单个元素并不有序，但左右两块是有序的（左边都小于基准数，右边都大于基准数），这就是conquer,继续对左右子数组进行同样操作，直到左右两块都是单个元素，这就是divide。

左右划分的实现

　　好的，既然思路已经有了，我们就来一步步实现吧，为了方便，依然使用Python。第一步将是关键的部分，以下是代码：（所有的说明全在注释里了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
__author__ = 'chen'
#事先用随机函数生成的数组
a = [92, 27, 26, 42, 24, 23, 5, 38, 95, 10, 42, 26, 81, 58, 17, 78, 14, 30, 55, 83, 61]
#以上函数级完成算法步骤1
def qs(a, s, e):        #a数组，s排序起始点，e排序结束点
    print a[s: e + 1]   #排印操作前的数组
    i = s               #左起始位：头
    j = e               #右起始位：尾
    k = (s + e) / 2     #以中间元素作为基准数（可任取）
    m = a[k]            #移动基准数到变量m（此时可视k位置为空缺）
    print "standard num : a[%d]=%d"%(k,m)   #打印调试信息
    
    #此实现从头部开始（尾部亦可）
    while i < j:
        while a[i] < m and i < j:   #找到大于基准数m的元素
            i += 1
        a[k] = a[i]                 #将其移动到空缺位（初值为基准数地址）
        k = i                       #元素已经移走，标注此处为空缺位
        
        #从尾部开始，寻找一个小于m的数来填充空缺
        while a[j] >= m and i < j:      #找到小于m的元素的地址
            j -= 1                      
        a[k] = a[j]                     #将其移动到空缺位
        k = j                           #更新空缺位，此时一个循环结束，下个循环继续从头部开始……
    
    #直到i，j相遇一次左右分列完成
    print "end at no.%d"%i
    a[i] = m            #记得将基准数放回空缺
    print a[s:e + 1]    #打印一次操作后的数组
qs(a, 0, len(a) - 1)

　　运行，输出如下 ：

1
2
3
4
[92, 27, 26, 42, 24, 23, 5, 38, 95, 10, 42, 26, 81, 58, 17, 78, 14, 30, 55, 83, 61]
standard num : a[10]=42      #基准数
end at no.11.               #i，j相遇位置（结束位）
[30, 27, 26, 14, 24, 23, 5, 38, 17, 10, 26, 42, 81, 58, 92, 78, 95, 42, 55, 83, 61]

　　可以看到，虽然看起来还是杂乱无章，但是以11号元素（42）为分割，左右分别是小于和大于（等于）它的数。

递归调用

　　至此步骤1就已经完成了，2,3实质为一步，只需要在函数qs(a,s,e)最后加上如下语句即可：

1
2
3
4
5
#对左右子数组继续同样操作
    if i>s:     #左子数组长为1则结束，否则继续
        qs(a,s,i)
    if i < e-1:   #右子数组长为1则结束，否则继续
        qs(a,i+1,e)

　　在文件最后加上print a之后，输出如下 ：（为了便于阅读，删除了部分输出）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
[92, 27, 26, 42, 24, 23, 5, 38, 95, 10, 42, 26, 81, 58, 17, 78, 14, 30, 55, 83, 61]
standard num : a[10]=42
end at a[11] = 26
[30, 27, 26, 14, 24, 23, 5, 38, 17, 10, 26, 42, 81, 58, 92, 78, 95, 42, 55, 83, 61]
[30, 27, 26, 14, 24, 23, 5, 38, 17, 10, 26, 42]
standard num : a[5]=23
end at a[4] = 24
[10, 17, 5, 14, 23, 30, 24, 38, 26, 27, 26, 42]
[10, 17, 5, 14, 23]
standard num : a[2]=5
end at a[0] = 10
[5, 17, 10, 14, 23]
[17, 10, 14, 23]
standard num : a[2]=10
end at a[1] = 17
[10, 17, 14, 23]
[17, 14, 23]
standard num : a[3]=14
end at a[2] = 17
[14, 17, 23]
[17, 23]
standard num : a[3]=17
end at a[3] = 17
[17, 23]
[30, 24, 38, 26, 27, 26, 42]
standard num : a[8]=26
end at a[6] = 24
[24, 26, 38, 30, 27, 26, 42]
……
[81, 58, 92, 78, 95, 42, 55, 83, 61]
standard num : a[16]=95
end at a[20] = 61
[81, 58, 92, 78, 61, 42, 55, 83, 95]
……
[5, 10, 14, 17, 23, 24, 26, 26, 27, 30, 38, 42, 42, 55, 58, 61, 78, 81, 83, 92, 95]

　　这样快速排序就完成了。实际实现的过程中遇到了一些小问题（毕竟程序一次写对的机率不大），主要是子数组的划分和循环结束的判定条件。

　　最好在划分子数组前加上if e-s>1:的判定条件，即：

1
2
3
4
5
if e - s > 1:
    if i > s:
        qs(a, s, i)
    if i < e - 1:
        qs(a, i + 1, e)

即可以优化算法（避免某些二元数组排序两遍）又可以避免出错（陷入死循环）。

性能比较

　　那么快速排序到底有多快？写了一个简单地冒泡法与之比较：

1
2
3
4
5
def bubble(b):
    for i in range(0, len(b)):
        for j in range(0, len(b) - i - 1):
            if b[j] > b[j + 1]:
                b[j], b[j + 1] = b[j + 1], b[j]

　　以相同的测试数组大小为20000,其代码与结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = []
for i in range(0, 20000):
    a.append(random.randint(0, 20000))
b = a[:]
start  = time.time()
qs(a, 0, len(a) - 1)
end  = time.time()
print end -start
start  = time.time()
bubble(b)
end  = time.time()
print end -start
print a[0:11],a[-11:-1]
print b[0:11],b[-11:-1]

输出如下 ：

1
2
3
4
0.0928180217743
35.1762809753
[0, 0, 1, 2, 3, 3, 5, 6, 7, 9, 11] [19985, 19988, 19989, 19989, 19992, 19993, 19993, 19993, 19996, 19997]
[0, 0, 1, 2, 3, 3, 5, 6, 7, 9, 11] [19985, 19988, 19989, 19989, 19992, 19993, 19993, 19993, 19996, 19997]

　　输出一致，但时间分别是0.093s和35.176s,差了300倍还多，可见 n*log(n) 与 n^2 的差异是十分明显的，而且随着输入规模的增加会更明显。

Contents
  1. 1. 分治法
  2. 2. 左右划分的实现
  3. 3. 递归调用
  4. 4. 性能比较