[已解决]找了好久没找到问题点- -！ 好无奈

iVi

视频看到递归，然后用递归写了一个快速排序代码如下：  

1. import random
   
2. def quick_sort(li):
   
3.     if len(li) < 2:
   
4.         return li
   
5.     else:
   
6.         flag = random.choice(li)
   
7. 
   
8.         lt = [i for i in li if i < flag]
   
9.         gt = [i for i in li if i > flag]
   
10. 
    
11.         return quick_sort(lt) + [flag] + quick_sort(gt)

复制代码

目前有个问题，排序倒是可以排序 但是如果 序列中有重复的 元素 将会被过滤掉如下图：

然后我就修改以下代码：

1. lt = [i for i in li if i <= flag]

复制代码

然后就。。。


找了好久没找到问题点- -！ 好无奈！！！

最佳答案

月排行榜 / 总排行榜

冬雪雪冬

2017-5-14 21:14:11

按你修改的，如果flag是最大数，则li=lt，递归无限循环下去。
这样就可以了。

1. import random
   
2. def quick_sort(li):
   
3.     if len(li) < 2:
   
4.         return li
   
5.     else:
   
6.         flag = random.choice(li)
   
7. 
   
8.         lt = [i for i in li if i < flag]
   
9.         gt = [i for i in li if i > flag]
   
10.         flag = [i for i in li if i == flag]
    
11. 
    
12.         return quick_sort(lt) + flag + quick_sort(gt)

复制代码

跳转到最佳答案楼层

冬雪雪冬

按你修改的，如果flag是最大数，则li=lt，递归无限循环下去。
这样就可以了。

1. import random
   
2. def quick_sort(li):
   
3.     if len(li) < 2:
   
4.         return li
   
5.     else:
   
6.         flag = random.choice(li)
   
7. 
   
8.         lt = [i for i in li if i < flag]
   
9.         gt = [i for i in li if i > flag]
   
10.         flag = [i for i in li if i == flag]
    
11. 
    
12.         return quick_sort(lt) + flag + quick_sort(gt)

复制代码

iVi

冬雪雪冬 发表于 2017-5-14 21:14
按你修改的，如果flag是最大数，则li=lt，递归无限循环下去。
这样就可以了。

谢啦