如何理解快速排序算法的思想？

Question

如题所述

Answer 1

#include <iostream>
using std::cout;
using std::endl;

int Partition( int *R, int low, int high){
// 对记录子序列 R[low..high] 进行一趟快速排序，并返回枢轴记录
// 所在位置，使得在它之前的记录的关键字均不大于它的关键字，
// 而在它之后的记录的关键字均不小于它的关键字
R[0] = R[low]; // 将枢轴记录移至数组的闲置分量
int pivotkey = R[low]; // 枢轴记录关键字
cout << endl << "pivotkey : " << pivotkey << endl;
while(low < high){ // 从表的两端交替地向中间扫描
while( low<high && R[high]>=pivotkey ){
--high;
}
if(low < high){//需要进行这样的判断，如果是由于low>=high而退出的循环，不需要移动数据
R[low++] = R[high]; // 将比枢轴记录小的记录移到低端
//cout << "移动的hign数据：" << R[high] << endl;
}
while (low<high && R[low]<=pivotkey )
++low;
if(low < high){
R[high--] = R[low]; // 将比枢轴记录大的记录移到高端
//cout << "移动的low数据：" << R[low] << endl;
}
} // while
R[low] = R[0]; // 枢轴记录移到正确位置
//cout << "返回的pivotkey: " << low << endl;
for(int i = 1; i<=10; i++){
cout << R[i-1] << " ";
}
return low; // 返回枢轴位置
} // Partition
void QSort(int *R, int s, int t ){
// 对记录序列 R[s..t] 进行快速排序
if (s < t){ // 长度大于1
int pivotloc = Partition(R, s, t);// 对 R[s..t] 进行一趟快排，并返回枢轴位置
QSort(R, s, pivotloc-1);//对低子序列递归进行排序
QSort(R, pivotloc+1, t);//对高子序列递归进行排序
}//if
}//Qsort
int main(){
int li[10] = {0,38,65,97,76,13,27,48,55,4};
cout<<"注意:R[0]为数组的闲置分量"<<endl;
for(int i = 1; i<=10; i++){
cout << li[i-1] << " ";
}
cout << endl;
QSort(li,1,9);
cout << endl;
for(int i = 1; i<=10; i++){
cout << li[i-1] << " ";
}
cout << endl;
return 0;
}