将两个值域互不相交的序列合并只需简单的合并两个序列。
所以我们只需将一个序列分成两个值域不相交的部分然后分别排序后合并就能解决排序的问题。
为了将序列分成值域不相交的两部分,可以选取一个值,将小于等于它的视作一个序列,大于它的视作另一个序列即可。
这就是快速排序表的基础思想
如图所示,对于一个序列可以进行快速排序
伪代码如下 algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] < pivot then
i := i + 1
swap A[i] with A[j]
if A[hi] < A[i + 1] then
swap A[i + 1] with A[hi]
return i + 1
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。