pythonAlgorithm/sort.py at master · yyzhy/pythonAlgorithm · GitHub

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
import random
x = 0
y = 0
def quickSort(num, l, r):
    global x
    x += 1
    if l >= r:
        return
    flag = l
    for i in range(l+1, r+1):
        if num[flag] > num[i]:
            tmp = num[i]
            del num[i]
            num.insert(flag, tmp)
            flag = flag + 1
    quickSort(num, l, flag - 1)
    quickSort(num, flag + 1, r)

def quickSortr(num, begin, end):
    global y
    y += 1
    if begin >= end:
        return
    k = random.randint(begin, end)
    tmp1 = num[begin]
    num[begin] = num[k]
    num[k] = tmp1
    flag = begin
    for i in range(begin+1, end+1):
        if num[flag] > num[i]:
            tmp2 = num[i]
            del num[i]
            num.insert(flag, tmp2)
            flag = flag + 1
    quickSortr(num, begin, flag - 1)
    quickSortr(num, flag + 1, end)

def printnum():
    global x, y
    print("01 quickSort has done " + str(x) + " times.")
    print("02 quickSortr has done " + str(y) + " times.")