C++实现快速排序算法

"快速排序是一种高效的排序算法，由C.A.R. Hoare在1960年提出。其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。此程序实现了一个模板化的快速排序算法，适用于不同类型的元素，如整数、字符等。" 快速排序的实现通常包括以下步骤： 1. **选择枢轴（Pivot）**: 在这段代码中，枢轴选取是数组中间的元素`array[s]`。在实际应用中，枢轴的选择策略会影响算法的效率，有多种策略可供选择，如“三数取中”（取首、尾、中间三个元素的中位数）。 2. **分区操作（Partition）**: 这部分代码定义了一个名为`Partion`的函数，它接收一个数组、起始下标`s`、结束下标`high`以及数组长度`n`作为参数。函数内部通过两个指针`low`和`high`分别从两端开始扫描数组。当`low`小于`high`时，会交换不满足条件的元素（`low`处的元素小于枢轴且`high`处的元素大于枢轴），直到`low`和`high`相遇。最后，将枢轴放置在其正确的位置，使得枢轴左边的元素都小于枢轴，右边的元素都大于枢轴。 3. **递归排序**：在`QSort`函数中，首先调用`Partion`函数对数组进行分区，然后分别对分区后的两部分数组进行递归调用`QSort`函数，直至子数组的大小为1或0，结束递归。这一步体现了快速排序的分治思想。 4. **主函数**：`main`函数中，首先输入数组的长度`n`和数组元素，然后调用`QSort`对数组进行排序，并在排序完成后输出排序后的数组。 快速排序的时间复杂度在最坏情况下为O(n²)，但平均情况下为O(n log n)，是目前应用最为广泛的排序算法之一。由于其原地排序（不需要额外的存储空间）和平均性能优异，快速排序在实际编程中非常实用。然而，对于已经部分排序或者数据分布极不均匀的数组，快速排序的效率可能会降低，这时可以考虑采用其他排序算法，如归并排序或堆排序。