How to Implement Quicksort Algorithm in Python – the Pytho
- 时间:2020-09-28 16:28:51
- 分类:网络文摘
- 阅读:102 次
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) --
推荐阅读:统计图沾上了污渍 佳佳从甲地往乙地走 小明每天下午五点放学 这个游戏规则公平吗 两枚硬币正面都朝上的可能性是几分之几 这根绳子一共被剪成多少段 扇形和半圆有重叠部分 为wordpress新建一个登录页面 wordpress自动显示图片exif信息插件-Display Exif 为wordpress设置一个简单的后台登陆地址
- 评论列表
-
- 添加评论