FilesExpand file tree

 master

/

QuickSort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (35 loc) · 1.23 KB

 master

/

QuickSort.py

Copy path

Top

File metadata and controls

• Code
• Blame

46 lines (35 loc) · 1.23 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# coding: utf-8

def quickSort(alist):

quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):

if first < last:

splitPoint = partition(alist, first, last)

quickSortHelper(alist, first, splitPoint-1)

quickSortHelper(alist, splitPoint+1, last)

def partition(alist, first, last):

pivotvlue = alist[first]

leftmark = first+1

rightmark = last

done = False

while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvlue: # bugfix: 先比较index, 不然数组会越界

leftmark += 1

while rightmark >= leftmark and alist[rightmark] >= pivotvlue:

rightmark -= 1

if leftmark > rightmark:

done = True

else:

alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]

alist[rightmark], alist[first] = alist[first], alist[rightmark]

return rightmark

alist = [54,26,93,17,77,31,44,55,20]

alist2 = [1]

quickSort(alist2)

print(alist2)

if __name__ == "__main__":

test_data = [3,2,111,3,-1,0,0,1,0,2,4]

res_stable = sorted(test_data)

quickSort(test_data)

print(test_data)

print(res_stable)

assert all(map(lambda x: x[0] == x[1], zip(res_stable, test_data)))