随机快速排序

《算法笔记》中摘取

//选取随机主元，对区间[left, right]进行划分
int randPartition(int A[], int left, int right) {
    //生成[left, right]内的随机数p
    int p = (round(1.0 * rand() / RAND_MAX * (right - left) + left);
    swap(A[p], A[left]); //交换A[left]存放至临时变量temp
    while(left < right) { //只要left与right不相遇
        while(left < right && A[right] > temp) right--; //反复左移right
        A[left] = A[right]; //将A[right]挪到A[left]
        while(left < right && A[left] <= temp) left--; //反复右移left
        A[right] = A[left]; //将A[left]挪到A[right]
    }
    A[left] = temp; //把temp放到left与right相遇的地方
    return left;    //返回相遇的下标
}