以第一个元素为快速排序的快速排序

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

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

the following code uses first element as pivot 

public static int[] qs(int[] list, int start, int end) { 
if (end - start <= 1) { 
    return list; 
} 
int pivot = split(list, start, end); 
qs(list, start, pivot); 
qs(list, pivot + 1, end); 
return list; 
} 

private static int split(int[] list, int start, int end) { 
int pivot = list[start]; 
int i = start; 
for (int j = start + 1; j <= end; j++) { 
    int current = list[j]; 
    if (current < pivot) { 
    swap(list, i + 1, j); 
    i++; 
    } 
} 
swap(list, start, i); 
return i; 
} 

private static void swap(int[] list, int i, int j) { 
int temp = list[i]; 
list[i] = list[j]; 
list[j] = temp; 
} 

Answer 3

/* Quick Sort taking first element as pivot element*/ 
void QuickSort(int* arr,int start,int last) 
{ 
    int i=start+1,j=last,temp; 
    if(i>j) 
    return; 
    while(i<=j) 
    { 
       if(arr[i]<arr[start]) 
       {enter code here 
           i++; 
       } 
       if(arr[j]>arr[start]) 
       { 
           j--;     
       } 
       if(i<=j) 
       { 
        temp=arr[i]; 
        arr[i]=arr[j]; 
        arr[j]=temp; 
       } 
     } 

     temp=arr[start]; 
     arr[start]=arr[j]; 
     arr[j]=temp; 

     QuickSort(arr,start,j-1); 
     QuickSort(arr,j+1,last); 
} 

对整个代码，请访问： - http://www.liladharpaliwal.blogspot.in/

Answer 4

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); 
} 
}