以第一个元素为例的快速排序 [英] Quicksort with first element as pivot example

问题描述

目前我正在快速排序，并想知道它是如何工作，当第一(或最后)元件被选作枢轴点.

I am currently studying quicksort and would like to know how it works when the first (or last) element is chosen as the pivot point.

例如，我有以下数组:

{15, 19, 34, 41, 27, 13, 9, 11, 44}

这是我认为的情况:

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^
pivot

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^                              ^
compare these two, they are good

{15, 19, 34, 41, 27, 13, 9, 11, 44}
 ^                          ^
compare these two and swap

{11, 19, 34, 41, 27, 13, 9, 15, 44}
 ^                       ^
compare these two and swap

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^                  ^
compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^              ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^          ^
compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^      ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}
 ^  ^
 compare these two, they are good

{9, 19, 34, 41, 27, 13, 11, 15, 44}

End of first partition

这是如何工作的?如果是这样，则将19作为新的枢轴点，还是将数组分成两半才能找到它(以至于将成为27/13)，还是取决于quicksort的实现?感谢您的宝贵时间！

Is this how it works? If so, would 19 be the new pivot point, or do you divide the array in half to find it (so that it would be 27/13), or does it depend on the implementation of the quicksort? Thanks for your time!

推荐答案

查看Wikipedia，有一个小例子，其中包含就地快速排序列表 http://en.wikipedia.org/wiki/Quicksort

Check wikipedia, there is a little example with a bit smaller list of inplace quicksort http://en.wikipedia.org/wiki/Quicksort

以您的示例为例，进行分区

With your example the idea is to partition

{15, 19, 34, 41, 27, 13, 9, 11, 44}

进入

{13, 9, 11 -- 15 -- 19, 34, 41, 27, 44}

所以首先我们将枢轴移到末端

So first we move pivot to the end

Swap 44, and 15
{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^                          ^

Than check 44, its larger than pivot, so swap with one one before last...

{11, 19, 34, 41, 27, 13, 9, 44, 15}
 ^                       ^

than check element at some position as last one was larger than pivot.
9 < 15, so proceed to the next, 19 > 15 => swap

{11, 9, 34, 41, 27, 13, 19, 44, 15}
        ^            ^

swap again
{11, 9, 13, 41, 27, 34, 19, 44, 15}
        ^       ^

next
{11, 9, 13, 41, 27, 34, 19, 44, 15}
            ^   ^

and second last swap

{11, 9, 13, 27, 41, 34, 19, 44, 15}
            ^    

Now as forward and backward indices reached each other,
we swap pivot into right position

{11, 9, 13, 15, 41, 34, 19, 44, 27}

我们得到了分区集.开头的项目少于15个，枢轴= 15，然后是更大的元素.

And we got partitioned set. Items less than 15 at the beginning, than pivot = 15, and then greater elements.

维基百科文章中描述的算法有些不同:

algorithm described in wikipedia article is a bit different:

Legend:
^ = storeindex
# = i

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^#

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^   #

... until ...   

{44, 19, 34, 41, 27, 13, 9, 11, 15}
 ^                   #

{13, 19, 34, 41, 27, 44, 9, 11, 15}
     ^                   #

{13, 9, 34, 41, 27, 44, 19, 11, 15}
        ^                   #

{13, 9, 11, 41, 27, 44, 19, 34, 15}
            ^                   #

{13, 9, 11, 15, 27, 44, 19, 34, 41}
            ^- pivot

这篇关于以第一个元素为例的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！