其实现在 新的pilot所指向的位置存放的值时arr[i]。(5)式显然是保持(2)式要求的。遍历完整个序列,得到最后的pilot,然后把pilot_value放到这个位置上,就可以了。最后查找pilot并整理序列以满足(2)式要求的函数实现如下(采用模板):
template <typename Type>
int find_pilot(Type arr[], int iLen) {
int my_pilot = 0;
int pilot_value = arr[0];
for (int i = 1; i != iLen; ++i) {
if (pilot_value > arr[i]) {
// pilot位置上放上arr[i]
arr[my_pilot] = arr[i];
// pilot自增
my_pilot++;
// pilot和arr[i]交换,以保证pilot指向的值无意义。
std::swap(arr[i], arr[my_pilot]);
}
}
arr[my_pilot] = pilot_value;
return my_pilot;
}
快速排序就是先通过上述函数将原始序列按pilot分为两个子序列,然后针对两个子序列分别递归调用,代码如下:
template <typename Type>
void quick_sort(Type arr[], int iLen) {
if (iLen <= 1) {
return;
}
int pilot = find_pilot(arr, iLen);
quick_sort(arr, pilot);
quick_sort(arr + pilot + 1, iLen - pilot - 1);
}
最后,我们测试代码如下:
int main() {
std::cout << "= = = = = 快速排序算法 = = = = =" << std::endl;
std::cout << "排序前的数组:";
int iTestArray[10] = { 0 };
srand((unsigned int)time(NULL));
for (int i = 0; i != 10; ++i) {
iTestArray[i] = rand() % 100;
std::cout << iTestArray[i] << " ";
}
std::cout << std::endl;
quick_sort(iTestArray, 10);
std::cout << "排序后的数组:";
for (int i = 0; i != 10; ++i) {
std::cout << iTestArray[i] << " ";
}
std::cout << std::endl;
return 0;
}
测试结果如下: