Quick Sort原理很简单,典型的分治法:
1,分
数组a一分为二,比元素x小或等的子数组和比元素x大的数组
2,递归
子数组递归分
3,合
子数组分好以后按序合并即可
用Ruby和Erlang实现Quick Sort实在简洁:
ruby:
def quick_sort(a)
(x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : []
end
erlang:
quick_sort([]) ->
[];
quick_sort([H | T]) ->
quick_sort([ X || X <- T, X < H ]) ++ [H] ++ quick_sort([ X || X <- T, X >= H ]).
最坏时间复杂度为O(n^2):
如果每次分的时候选取的元素都是最小或最大值,那么分完以后就会出现一边为空一边为除了选取元素外所有元素的数组,复杂度为1+2+...+n = O(n^2)
最好时间复杂度为Θ(nlogn):
如果每次分的时候选取的元素都是中间值,那么分完以后两边的数组size一样大:
T(n) = 2T(n/2) + Θ(n) = Θ(nlogn)
分享到:
相关推荐
CLRS 最后,要拿 LeetCode,Python 可以让你专注于想法,而 CLRS 真的有点乏味,所以每当你读完时,你就会感到很高兴,因为你可以做 LeetCode。 :books: :open_book: :pencil: :notebook: :hamburger: :spaghetti: :...
算法简介第3版 托马斯·科门(Thomas H.Cormen) 查尔斯·莱森(Charles E.Leiserson) 罗纳德·里维斯特(Ronald Rivest) 克利福德·斯坦
CLRS教材练习算法关于该项目重点在于通过在代码中实现对基本和高级数据结构及算法的掌握。 这主要是在Python中完成的。促成主题分叉项目创建功能分支( git checkout -b feature/AmazingFeature ) 提交更改( git ...
CLRS(Introduction.to.Algorithms.Second.Edition)
CLRS英文第二版 .
clrs-notes-solutions, 算法导论,第3版,学习笔记,习题答案
一个个人帮助页面,用于准备数据结构和算法,重点是CLRS书籍... /src目录是添加各种算法的实现的位置。 该README.md文件用于列出数据结构和算法,而不一定来自本书。 快速浏览 目录 Sl。 话题 1。 :check_box_...
CLRS CLRS 代码
在有关算法的书中,有一些叙述非常严谨,但不够全面;另一些涉及了大量的题材,但又缺乏严谨性。《算法导论(原书第3版)》将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的...
大名鼎鼎的 CLRS Algorithm Introduction 算法导论 课后大部分的题目解答
算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm
指《算法导论》(Introduction to Algorithms)。 由Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein编写,MIT出版的一本介绍、分析当代计算机...用四位作者姓的首字母组成的CLRS代表此书。
算法导论 CLRS 英文第三版 算法导论 CLRS 英文第三版
CLRS Problems 15-5 的解法
MIT算法分析教材CLRS的教师手册,内有课程精讲及习题答案
CLRS CLRS示例代码的C ++实现和研究目的。 不涉及编码的练习将不会共享。
clrs CLRS算法的实现
算法导论CLRS 英文第3版 pdf 是算法方面的经典著作
algorithms from CLRS "Introduction to Algorithms 3rd" implementation in C++ templates. 《算法导论》第三版 C++泛型实现
算法導論第三版习题答案