《算法导论》伪代码C++实现--快速排序_快速排序算法c++伪代码

《算法导论》第7章快速排序

/**
 * 快速排序
 */
#include <bits/stdc++.h>
using namespace std;

int partition(int A[], int p, int r){
    int i = p-1;
    for (int j = p; j <= r-1; ++j) {
        if (A[j] <= A[r]){
            i++;
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    int temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp;
    return i+1;
}

void quickSort(int A[], int p, int r){
    if(p<r){
        int q = partition(A,p,r);
        quickSort(A, p, q-1);
        quickSort(A, q+1, r);
    }
}

int main(){

    //数组A[0]忽略，从A[1]开始
    int A[] = {0,4,1,3,2,16,9,10,14,8,7};
    int len = sizeof(A)/ sizeof(A[0]) - 1;

    quickSort(A,1,len);

    for (int i = 1; i <= len; ++i) {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}