20行代码实现快速排序

20行代码实现快速排序

1. def quickSort (arr):
   
2.     """ Quicksort a list
   
3. 
   
4.     :type arr: list
   
5.     :param arr: List to sort
   
6.     :returns: list -- Sorted list
   
7.     """
   
8.     if not arr:
   
9.         return []
   
10.     pivots  = []
    
11.     lesser  = []
    
12.     greater = []
    
13.     for x in arr:
    
14.         if x==arr[0]:
    
15.            pivots.append(x)
    
16.         elif x>arr[0]:
    
17.             greater.append(x)
    
18.         else:
    
19.             lesser.append(x)
    
20.     return quickSort(lesser) + pivots + quickSort(greater)
    
21. 
    
22. test_array = [1,4,5,7,8,9,90,3,2,3,4]
    
23. sorted_array = quickSort (test_array)
    
24. print "unsorted:",test_array,"Sorted:",sorted_array

复制代码

这。。浪费空间啊

深谙 发表于 2014-11-19 22:45
这。。浪费空间啊

呃。。。请给一个更高效的吧

test_array = [1,4,5,7,8,9,90,3,2,3,4]             print test_array.sort()

test_array = [1,4,5,7,8,9,90,3,2,3,4]             print（sorted(test_array））

mou.. 发表于 2016-11-15 15:47
test_array = [1,4,5,7,8,9,90,3,2,3,4]             print（sorted(test_array））

你这个肯定更快，因为你使用的内置函数， 我们的目的是构建算法

有点像二分法排，确实有点浪费空间。