Question

我目前正在迅速研究,并想知道,在选择第一个(或最后一个)要素作为起点时,它是如何运作的。

Say for example I have the following array:

{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。

With your example the idea is to partition

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

页: 1

{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 页: 1 right position

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

我们分门别类。最初的项目不到15件,而不是pivot = 15件,然后是更多的内容。

EDIT:维基百科文中描述的算法有点不同:

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 for last element as pivot

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 for first element as pivot

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

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/“rel=“nofollow” http://www.liladharpaliwal.blogspot.in/

Answer 4

选择第1项内容作为序号......

class QuickSortPart1{
    public int partition(int[] a, int left, int right) {
        int pivot = a[left];
        while(left<=right) {
            while(a[left] < pivot)
                left++;
            while(a[right] > pivot)
                right--;
            if(left<=right) {
                int tmp = a[left];
                a[left] = a[right];
                a[right] = tmp;
                left++;
                right--;
            }
        }
        return left;
    }
    public void recursiveQuickSort(int[] a, int i, int j) {
       int idx = partition(a, i, j);
       if(i < idx-1) {
           recursiveQuickSort(a, i, idx-1);
        }
       if(j > idx) {
           recursiveQuickSort(a, idx, j);
        }
    }

    void printarray(int arr[]){
        int len = arr.length;
        for(int i=0; i<len; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String[] args) {
        int arr[] = new int[]{5,8,1,3,7,9,2};
            System.out.print(arr[i]+" ");
        System.out.println("
");
        QuickSortPart1 ob = new QuickSortPart1();
        ob.recursiveQuickSort(arr, 0, arr.length-1);
        ob.printarray(arr);
    }
}

Answer 5

Try this algo: https://www.youtube.com/watch?v=7h1s2SojIRw

Base idea: All elements to left are smaller than all elements to the right then the element is said to be in sorted position.

Algo:

// partition
 Partition(l,h) {
     pivot = A[l];
     i=l; j=h;

     while(i<j) {
         do {
             i++;
         } while(A[i]<=pivot);

         do {
             j--;
         } while(A[j]>pivot);

         if(i<j) {
             swap(i,j);
         }
     }

     swap(A[l], A[j]);

     return j;
 }

 // quicksort
 QuickSort(l,h) {
     pi = Partition(l, h);
     QuickSort(l, pi);
     QuickSort(pi+1, h);
 }

Answer 6

这是一种快速的例子,即2个点从起点到中间点,同时比较和安放点;抽打,使用第一点作为纸浆,这是一种不同于Introduction to Algorithms的做法。

void quick_sort(vector<int>& vs, int l, int r)
{
  if(l >= r) return; // recursion end condition
  int pivot = vs[l];
  int first=l, last=r;
  while(first < last)
  {
    while(first < last && vs[last] > pivot)
      --last;
    vs[first] = vs[last];

    while(first < last && vs[first] <= pivot)
      ++first;
    vs[last] = vs[first];
  }
  vs[first] = pivot;         // first is the final index for pivot
  quick_sort(vs, l, first);
  quick_sort(vs, first+1, r);
}

Answer 7

import java.security.SecureRandom;

public class QuickSort {
    static  int ArraySize = 35;

    public static void main(String[] args) {
        SecureRandom generator = new SecureRandom();
        int[] array = generator.ints(ArraySize ,1,191).toArray();

        QuickSort qs = new QuickSort();
        qs.displayArray(array);
        int last = array.length-1;
        qs.quickSortHelper(array, 0, last);
        qs.displayArray(array);
    }//end method main

    public void quickSortHelper(int[] array, int starting, int ending){
       int partPos = partition(array, starting, ending);
       if(partPos-1 > starting) {
           quickSortHelper(array, starting, partPos-1);
       }
       if(partPos < ending) {
           quickSortHelper(array, partPos, ending);
       }
    }//end method quickSortHelper
    public int partition(int[] array, int lSide, int rSide){
        int partingVal = array[lSide];
        do {
            for (;array[rSide] > partingVal; rSide--){}
            for (;array[lSide] < partingVal;  lSide++){}
            if(rSide>=lSide) {
                int tempIndex = array[lSide];
                array[lSide] = array[rSide];
                array[rSide] = tempIndex;
                rSide--;
                lSide++;
            }
        }while(lSide<=rSide);
        return lSide;
    }//end method partitioin

    public void displayArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println("");
    }//end method displayArray
}//end class QuickSort

Answer 8

I found this easier to understand:

template <typename T>
unsigned int partition(T* input, unsigned int first, unsigned int last)
{
    T pivot = input[first];
    auto partitionIndex = first;

    // search for first position for partition index
    for(auto i=first; i<=last; ++i){
        if(input[i]>pivot){
            partitionIndex = i;
            break;
        }
    }

    for(auto i = partitionIndex; i<=last; ++i){
        if(input[i] <= pivot){
            std::swap(input[i],input[partitionIndex]);
            ++partitionIndex;
        }
    }

    std::swap(input[first],input[partitionIndex-1]);

    return partitionIndex-1;
}

template <typename T>
void quick_sort(T* input, unsigned int first, unsigned int last)
{
    if(first>=last) return ;

    auto divide_point = partition(input, first, last);

    quick_sort(input, first, divide_point-1);
    quick_sort(input, divide_point+1, last);
}

Answer 9

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

友情链接