其实就是一个快速排序算法的问题,哪个哥们能刚这看看
发布网友
发布时间:2022-05-02 00:18
我来回答
共1个回答
热心网友
时间:2022-05-22 02:48
将两个值域互不相交的序列合并只需简单的合并两个序列。
所以我们只需将一个序列分成两个值域不相交的部分然后分别排序后合并就能解决排序的问题。
为了将序列分成值域不相交的两部分,可以选取一个值,将小于等于它的视作一个序列,大于它的视作另一个序列即可。
这就是快速排序表的基础思想
如图所示,对于一个序列可以进行快速排序
伪代码如下
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