快速排序是一种高效的、基于分治思想的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本步骤包括选择一个“基准”元素，将数组分为两个子序列，使得一个子序列的所有元素都比基准小，另一个子序列的所有元素都比基准大，然后对这两个子序列递归地进行快速排序。这个过程会持续到子序列只剩下一个元素，最终整个序列就被排序好了。
在C++中，我们可以利用模板函数来实现通用的快速排序。我们需要定义一个交换元素的函数，用于在数组中交换两个位置的元素。接下来，定义一个划分函数，它接收一个数组、起始索引、结束索引以及基准元素的索引。这个函数会根据基准元素将数组划分为两部分，并返回基准元素的新位置。我们编写快速排序函数，它会递归调用自身对左右子序列进行排序。
以下是一个简单的C++快速排序算法实现示例：
```cpp
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int A[], int size) {
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
```
在这个代码中，`swap`函数用于交换数组中的两个元素，`partition`函数执行划分操作，`quickSort`是快速排序的主要函数，而`printArray`用于输出排序后的数组。在`main`函数中，我们创建了一个未排序的数组并调用`quickSort`进行排序，最后显示排序结果。
快速排序的平均时间复杂度为O(n log n)，在最坏的情况下（即输入数组已经完全排序或逆序）时间复杂度为O(n^2)。尽管如此，由于快速排序的常数因子较小，实际性能通常优于其他O(n log n)的排序算法。此外，快速排序在内部使用了原地排序，不需要额外的存储空间，因此在空间效率上也有优势。
在实际应用中，为了提高快速排序的性能，可以采用一些优化策略，比如随机选择基准元素以减少最坏情况的发生概率，或者在子序列规模较小的时候切换到插入排序等简单排序算法。这些优化可以使快速排序在大多数情况下表现出优秀的性能。
