Python 排序算法6：快速排序(2)

qiuyouzhi

Python 排序算法：快速排序(2)

实现快速排序
实现快排有两种方法：
1，双边循环法
2，单边循环法

双边循环法
假设这里有一个列表：

1. [4, 7, 6, 5, 3, 2, 8, 1]

复制代码

它的排序结果：

1. 1   left
   
2. [4, 7, 6, 5, 3, 2, 8, 1]
   
3. 6   right
   
4. [4, 1, 6, 5, 3, 2, 8, 7]
   
5. 5   right
   
6. [4, 1, 6, 5, 3, 2, 8, 7]
   
7. 2   left
   
8. [4, 1, 6, 5, 3, 2, 8, 7]
   
9. 4   right
   
10. [4, 1, 2, 5, 3, 6, 8, 7]
    
11. 3   left
    
12. [4, 1, 2, 5, 3, 6, 8, 7]
    
13. 3   right
    
14. [4, 1, 2, 3, 5, 6, 8, 7]
    
15. 1   left
    
16. [3, 1, 2, 4, 5, 6, 8, 7]
    
17. 2   left
    
18. [3, 1, 2, 4, 5, 6, 8, 7]
    
19. 1   left
    
20. [2, 1, 3, 4, 5, 6, 8, 7]
    
21. 6   right
    
22. [1, 2, 3, 4, 5, 6, 8, 7]
    
23. 5   right
    
24. [1, 2, 3, 4, 5, 6, 8, 7]
    
25. 4   right
    
26. [1, 2, 3, 4, 5, 6, 8, 7]
    
27. 6   right
    
28. [1, 2, 3, 4, 5, 6, 8, 7]
    
29. 5   right
    
30. [1, 2, 3, 4, 5, 6, 8, 7]
    
31. 7   left
    
32. [1, 2, 3, 4, 5, 6, 8, 7]
    
33. [1, 2, 3, 4, 5, 6, 7, 8]

复制代码

代码：

1. def quickSort(arr, begin, end):
   
2.     if begin > end:
   
3.         return None
   
4.     pivotIndex = partition(arr, begin, end)
   
5.     quickSort(arr, begin, pivotIndex - 1)
   
6.     quickSort(arr, pivotIndex + 1, end)
   
7. 
   
8. def partition(arr, begin, end):
   
9.     pivot = arr[begin]
   
10.     left = begin
    
11.     right = end
    
12. 
    
13.     while left != right:
    
14.         while left < right and arr[right] > pivot:
    
15.             right -= 1
    
16.             print(right, '  right')
    
17.             print(arr)
    
18.             
    
19.         while left < right and arr[left] <= pivot:
    
20.             left += 1
    
21.             print(left, '  left')
    
22.             print(arr)
    
23. 
    
24.         if left < right:
    
25.             arr[left], arr[right] = arr[right], arr[left]
    
26.             #print(arr)
    
27. 
    
28.     arr[begin] = arr[left]
    
29.     arr[left] = pivot
    
30. 
    
31.     return left
    
32. 
    
33. array = [4, 7, 6, 5, 3, 2, 8, 1]
    
34. quickSort(array, 0, len(array)-1)
    
35. print(array)

复制代码

(这里把print也加了进去，就是为了方便理解)

在下一节，我们会编写出单边循环法的快排！