快速排序（Quick Sort）是一种常用的排序算法，基本原理是通过选择一个基准元素，将数组分割成两部分，一部分的元素都小于基准，另一部分的元素都大于基准，然后对这两部分分别递归地进行快速排序，最终得到一个有序序列。
快速排序的基本原理如下：
1. **选择基准元素**：从数组中选择一个基准元素（通常选择第一个元素、最后一个元素或者随机选择），将数组分为两部分。
2. **分割操作**：重新排列数组，将小于基准元素的放在基准元素的左边，大于基准元素的放在右边，基准元素放在中间。
3. **递归排序**：对基准元素左右两部分分别递归进行快速排序。
快速排序的特点：
- 快速排序是一种不稳定的排序算法，相同元素的相对位置可能改变。
- 平均时间复杂度为 O(n log n)，最坏情况下为 O(n^2)。
- 快速排序是原地排序算法，不需要额外的空间。
快速排序在实际应用中表现优异，尤其在大规模数据的排序中效率较高。以下是用 C++ 实现快速排序的示例代码：
```cpp #include <iostream> #include <vector> int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::vector<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(const std::vector<int>& arr) { for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; } int main() { std::vector<int> arr = {10, 7, 8, 9, 1, 5}; int n = arr.size(); std::cout << "Original array: "; printArray(arr); quickSort(arr, 0, n - 1); std::cout << "Sorted array: "; printArray(arr); return 0; } ```
在这段代码中，`partition` 函数用于将数组分割为两部分，并返回基准元素的位置，`quickSort` 函数实现了快速排序算法，`printArray` 函数用于打印数组的元素。在 `main` 函数中定义了一个整型数组并对其进行快速排序。
