快速排序算法及其测试算法的原理与实现

快速排序简介

快速排序是一种分治的排序算法，是实践中最快的排序算法，理论上的时间复杂度为O(N*lgN)，最差情况的时间复杂度为O(N^2)，但稍加努力就可避免这种情况。

快速排序的步骤

  1. 如果列表中的元素为0或1个，则返回
  2. 选取标记值p
  3. 将列表分为两部分s1、s2，需满足条件：s1中的元素均小于或等于p，s2中的元素均大于等于p，得到s1+p+s2
  4. 对s1、s2重复2、3步骤，最终得到排序结果

从上面的步骤可以看出，快速排序需要递归运算。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def median3(L,a,b,c):
    if L[a] >= L[b] and L[b] >= L[c]:
        mid = L[b]
        i = b
    elif L[a] <= L[b] and L[b] <= L[c]:
        mid = L[b]
        i = b
    elif L[b] >= L[a] and L[a] >= L[c]:
        mid = L[a]
        i = a
    elif L[b] <= L[a] and L[a] <= L[c]:
        mid = L[a]
        i = a
    else:
        mid = L[c]
        i = c
    return [mid,i]  
def swap(L, i, j):
    tmp = L[i]
    L[i] = L[j]
    L[j] = tmp
def quickSort(L, low, high):
    if low < high:
        i = low
        j = high
        meta = median3(L, i, (i+j)/2, j)
        pivot = meta[0]
        pivotPos = meta[1]
        # move pivot to the right end
        swap(L, pivotPos, high) 
        
        while i < j:
            # pivot on the right end, starting from left
            while i < j and L[i] <= pivot:
                i = i+1
            while j > i and L[j] >= pivot:
                j = j-1
            swap(L, i, j)
        # move pivot to right position
        swap(L, i, high)
        
        quickSort(L, low, i-1)
        quickSort(L, i+1, high)

测试算法

排序结果正确，需满足条件

  1. 列表除元素顺序变化外，没有别的变化
  2. 列表中的元素是有序的

条件2容易实现，重点关注条件1

如何确保列表除元素顺序变化外，没有别的变化？

列表L1、L2满足以下三个条件即可

  1. L1、L2中的元素数量相同
  2. L1、L2的元素组成的集合相同（L1中的元素都在L2中，反之也成立）
  3. L1、L2中元素的和相同

例如，列表L1=[2,3,2,2,3]，顺序打乱后得到L2=[2,2,3,3,2]，此时L1、L2满足以上三个条件。如果对L2进行以下操作，均会使其中的一个或多个条件不成立。

  • 添加/删除元素
  • 修改元素值

测试算法实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys
import random
import copy
# condition 2
def diff2List(l1,l2):
    diff = [val for val in l1 if val not in l2]
    for v in [val for val in l2 if val not in l1]:
        diff.append(v)
    return diff
def isListSorted(L):
    i = 0
    while i < len(L) - 2:
        if L[i] <= L[i+1]:
            i = i+1
        else:
            return [i, L[i], L[i+1]]
    return True
# condition 3
def sumList(L):
    sum = 0
    for i in L:
        sum = sum + i
    return sum
def randomList(length, maximum):
    l = []
    i = 0
    while i < length:
        l.append(random.randint(0, maximum))
        i = i+1
    return l
#
# Test usage: python <script_path> <test_times> <min_list_length> <max_list_length> <max_list_element_value>
#
testTimes = int(sys.argv[1])
minLength = int(sys.argv[2])
maxLength = int(sys.argv[3])
maxValue = int(sys.argv[4])
for i in range(testTimes):
    L = randomList(random.randint(minLength, maxLength), maxValue)
    print 'Test round #' + str(i)
    # original
    print L
    # deep copy for test
    tmpList = copy.deepcopy(L)
    quickSort(L, 0, len(L) - 1)
    if len(L) != len(tmpList) or diff2List(L, tmpList) != [] or sumList(L) != sumList(tmpList):
        print 'Bad #not coherent'
        break
    else:
        sorted = isListSorted(L)
        if sorted != True:
            print 'Bad #not sorted'
            print sorted
            break
    # after sort
    print L