Python 排序算法7： 快速排序（3）

qiuyouzhi

Python 排序算法： 快速排序（3）

单边循环法

昨天那个双边循环法，大家看着很迷糊吧？
一个大循环，里面套这两个小循环，肯定得晕。。
那么今天就来一个代码少一些，partition实现起来也简单一些的单边循环法！

代码：

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.     mark = begin
    
11. 
    
12.     for i in range(begin, end+1):
    
13.         if arr[i] < pivot:
    
14.             mark += 1
    
15.             print(mark)
    
16.             arr[i], arr[mark] = arr[mark], arr[i]
    
17.             print(arr)
    
18. 
    
19.     arr[begin] = arr[mark]
    
20.     arr[mark] = pivot
    
21.     return mark
    
22. 
    
23. arr = [4, 4, 6, 5, 3, 2, 8, 1]
    
24. quickSort(arr, 0, len(arr)-1)
    
25. print(arr)

复制代码

一个账号

没放进专辑？

qiuyouzhi

一个账号 发表于 2020-3-7 09:37
没放进专辑？

啊啊啊啊啊啊
我为什么老是忘啊啊啊

一个账号

qiuyouzhi 发表于 2020-3-7 09:40
啊啊啊啊啊啊
我为什么老是忘啊啊啊

(2) 好像没放进专辑