How to Implement Quicksort Algorithm in Python – the Pytho
- 时间:2020-09-28 16:28:51
- 分类:网络文摘
- 阅读:90 次
In here, we talk about the implementation of QuickSort in Python – the well-known and standard sorting algorithm that is used today.
It is not so easy to implement except in Python, in a Pythonic way. The quicksort algorithm can be easily illustrated using the following Python recursion function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution(object): def sortArray(self, nums): """ :type nums: List[int] :rtype: List[int] """ if len(nums) < = 1: return nums pivot = random.choice(nums) lt = [v for v in nums if v < pivot] eq = [v for v in nums if v == pivot] gt = [v for v in nums if v > pivot] return self.sortArray(lt) + eq + self.sortArray(gt) |
class Solution(object): def sortArray(self, nums): """ :type nums: List[int] :rtype: List[int] """ if len(nums) < = 1: return nums pivot = random.choice(nums) lt = [v for v in nums if v < pivot] eq = [v for v in nums if v == pivot] gt = [v for v in nums if v > pivot] return self.sortArray(lt) + eq + self.sortArray(gt)
First, we choose a random pivot, then we partition the input array into three parts, then recursively partition left, and right parts, finally merge into a new list.
The downside of above implementation is it requires additional O(N) space, which can be eliminated using in-place swapping.
Depending on the randomness when choosing a good pivot, the performance of the quicksort may vary. The worst cases would be O(N^2), and average complexity is O(Nlog(N))
This implementation is easy to remember and easy to write on coding whiteboard. And it is code that works rather than pseudo-code.
Recursive Quicksort implementation in Javascript: Javascript Coding Exercise: The QuickSort Implementation in Javascript
--EOF (The Ultimate Computing & Technology Blog) --
推荐阅读:熟知百度蜘蛛原理,按照优化规则才能做好seo优化 SEO关键词排名优化原理是什么? 织梦程序如何调用自定义字段? 旅途遇见美 不再遗失的美好 美丽的三亚作文600字 最后的六一作文650字 疲惫并快乐着 小议“先天下之忧而忧,后天下之乐而乐”作文450字 鸳鸯湖作文
- 评论列表
-
- 添加评论