QuickSort—MIT算法导论

https://github.com/yuanoOo/Algorithm/tree/master/SortAlgorithm/QuickSort

伪代码

• ★PARTITION

PARTITION(A,p,r)
   x = A[r]   //将最后一个元素作为主元素
  i = p-1
   for j=p to r-1     //从第一个元素开始到倒数第二个元素结束，比较确定主元的位置
       do if A[j] <= x
             i = i+1
             exchange A[i] <-> A[j]
   exchange A[i+1]<->A[r]   //最终确定主元的位置
   return i+1   //返回主元的位置

• QUICKSORT

QUICKSORT(A,p,r)
     if p<r
        q = PARTITION(A,p,r)    //确定划分位置
        QUICKSORT(A,p,q-1)     //子数组A[p...q-1]
        QUICKSORT(Q,q+1,r)     //子数组A[q+1...r]

• 随机化版本

 RANDOMIZED-PARTITION(A,p,r)
    i = RANDOM(p,r)
    exchange A[r] <->A[i]
    return PARTITION(A,p,r)

code

#include<iostream>
using namespace std;

int partition(int *A, int low, int high);
void swap(int *a, int low, int high);
void quickSort(int *A, int low, int high);
void print(int *A, int low, int high);

int main()
{
    int A[] = {2, 6, 3, 10, 45, 12, 5, 6, 5, 6};
    quickSort(A, 0, 9);
    print(A,0,9);
}

//end:A中最后一个元素的index，非length of A 
int partition(int *A, int low, int high)
{
    //select the last element as position, position is not index
    int position = A[high];
    //在数组最开始的前面建立空间 
    int i = low - 1;
    
    for(int j = low; j < high; j++)
    {
        if(A[j] <= position)
        {
            ++i;
            swap(A, j, i); 
        }
    }
    
    swap(A, i+1, high);
    return i+1;
}

void quickSort(int *A, int low, int high)
{
    int q;
    if(low < high)
    {
        q = partition(A,low,high);
        quickSort(A, low, q - 1);
        quickSort(A, q + 1, high);
    }
}

void swap(int *a, int low, int high)
{
    int temp = a[low];
    a[low] = a[high];
    a[high] = temp;
}

void print(int *A, int low, int high)
{
    for(int i = low; i <= high; i++)
        cout<<A[i]<<"、"; 
}