快速排序算法c++（快速排序算法csdn）

## 快速排序算法 C++### 简介快速排序（Quick Sort）是一种高效的排序算法，其基本思想是

分治

。它通过选择一个“基准”（pivot）元素，将待排序序列分成两个子序列：小于等于基准元素的子序列和大于基准元素的子序列。然后递归地对这两个子序列进行排序，最终得到有序序列。### 算法步骤1.

选择基准元素：

可以选择序列的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准元素。2.

分区：

将序列中小于等于基准元素的元素放到基准元素的左边，大于基准元素的元素放到右边。3.

递归排序：

递归地对基准元素左边的子序列和右边的子序列进行快速排序。### 代码实现```c++ #include using namespace std;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); } }int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);cout << "排序后的数组: " << endl;for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0; } ```### 详细说明

partition() 函数：

该函数接受一个数组 `arr`，以及要分区的子数组的起始索引 `low` 和结束索引 `high`。

选择最后一个元素作为基准元素 `pivot`。

使用两个指针 `i` 和 `j` 遍历子数组。

`i` 指向小于 `pivot` 的元素的最后一个位置，`j` 指向当前遍历到的元素。

如果 `arr[j]` 小于 `pivot`，则将 `i` 加 1，并将 `arr[i]` 和 `arr[j]` 交换位置，确保小于 `pivot` 的元素都在 `pivot` 的左边。

最后将 `pivot` 与 `i + 1` 位置的元素交换，将 `pivot` 放到正确的位置。

返回 `pivot` 的索引。

quickSort() 函数：

该函数接受一个数组 `arr`，以及要排序的子数组的起始索引 `low` 和结束索引 `high`。

如果 `low` 小于 `high`，则调用 `partition()` 函数对子数组进行分区，并将返回的 `pivot` 索引存储在 `pi` 中。

递归地调用 `quickSort()` 函数对 `pivot` 左边和右边的子数组进行排序，直到整个数组有序。### 算法复杂度

时间复杂度:

最佳情况：O(n log n)，当每次分区都能将数组分成大小相等的两个子数组时。

平均情况：O(n log n)

最坏情况：O(n^2)，当数组已经有序或逆序时。

空间复杂度:

O(log n)，递归调用栈的空间。### 总结快速排序是一种高效的排序算法，在平均情况下表现优异。它实现简单，应用广泛，是许多排序库函数的首选算法。

快速排序算法 C++

简介快速排序（Quick Sort）是一种高效的排序算法，其基本思想是**分治**。它通过选择一个“基准”（pivot）元素，将待排序序列分成两个子序列：小于等于基准元素的子序列和大于基准元素的子序列。然后递归地对这两个子序列进行排序，最终得到有序序列。

算法步骤1. **选择基准元素：** 可以选择序列的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准元素。2. **分区：** 将序列中小于等于基准元素的元素放到基准元素的左边，大于基准元素的元素放到右边。3. **递归排序：** 递归地对基准元素左边的子序列和右边的子序列进行快速排序。

代码实现```c++

include using namespace std;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); } }int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);cout << "排序后的数组: " << endl;for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0; } ```

详细说明* **partition() 函数：*** 该函数接受一个数组 `arr`，以及要分区的子数组的起始索引 `low` 和结束索引 `high`。* 选择最后一个元素作为基准元素 `pivot`。* 使用两个指针 `i` 和 `j` 遍历子数组。* `i` 指向小于 `pivot` 的元素的最后一个位置，`j` 指向当前遍历到的元素。* 如果 `arr[j]` 小于 `pivot`，则将 `i` 加 1，并将 `arr[i]` 和 `arr[j]` 交换位置，确保小于 `pivot` 的元素都在 `pivot` 的左边。* 最后将 `pivot` 与 `i + 1` 位置的元素交换，将 `pivot` 放到正确的位置。* 返回 `pivot` 的索引。* **quickSort() 函数：*** 该函数接受一个数组 `arr`，以及要排序的子数组的起始索引 `low` 和结束索引 `high`。* 如果 `low` 小于 `high`，则调用 `partition()` 函数对子数组进行分区，并将返回的 `pivot` 索引存储在 `pi` 中。* 递归地调用 `quickSort()` 函数对 `pivot` 左边和右边的子数组进行排序，直到整个数组有序。

算法复杂度* **时间复杂度:** * 最佳情况：O(n log n)，当每次分区都能将数组分成大小相等的两个子数组时。* 平均情况：O(n log n)* 最坏情况：O(n^2)，当数组已经有序或逆序时。 * **空间复杂度:** O(log n)，递归调用栈的空间。

总结快速排序是一种高效的排序算法，在平均情况下表现优异。它实现简单，应用广泛，是许多排序库函数的首选算法。