以第一个元素为枢轴示例的快速排序

Question

我目前正在研究快速排序，想知道当第一个（或最后一个）元素被选为轴心点时它是如何工作的。

例如说我有以下数组：

{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），还是取决于快速排序的实现？谢谢你的时间！

Answer 1

检查维基百科，有一个小示例，其中包含一个较小的就地快速排序列表http://en.wikipedia.org/wiki/Quicksort

用你的例子，这个想法是分区

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

进入

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

所以首先我们将枢轴移到最后

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 的项目，大于 pivot = 15，然后是更大的元素。

编辑：维基百科文章中描述的算法有点不同：

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

Answer 2

https://www.youtube.com/watch?v=COk73cpQbFQ 用于作为枢轴的最后一个元素

int partition(int *a,int start,int end)

{

int pivot=a[end],temp,p1=start,i;

for(i=start;i<end;i++)
{
    if(a[i]<pivot)
    {
        if(i!=p1)
        {
            temp=a[p1];
            a[p1]=a[i];
            a[i]=temp;
        }
        p1++;
    }
}

        temp=a[p1];
        a[p1]=a[end];
        a[end]=temp;
return p1;
}

https://www.youtube.com/watch?v=6UHCG64tHgo 将第一个元素作为枢轴

 int partition1(int *a,int start,int end)

{

int pivot=a[start],p1=start+1,i,temp;

for(i=start+1;i<=end;i++)
{

if(a[i]<pivot)
    {
        if(i!=p1)
      {  
            temp=a[p1];
            a[p1]=a[i];
            a[i]=temp;
      }    p1++;
    }
}

        a[start]=a[p1-1];
        a[p1-1]=pivot;

return p1-1;
}




  void quicksort(int *a,int start,int end)
{
 int p1;
 if(start<end)
{
    p1=partition(a,start,end);
    quicksort(a,start,p1-1);
    quicksort(a,p1+1,end);
}
}