快速排序算法c++代码（快速排序的c语言实现）

## 快速排序算法 C++ 代码### 简介快速排序（Quicksort）是一种高效的排序算法，其平均时间复杂度为 O(n log n)。它采用分治策略，将一个序列分成两个子序列，并递归地对子序列进行排序。### 算法步骤1.

选择基准元素（Pivot）：

从序列中选择一个元素作为基准元素，通常选择第一个、最后一个或中间的元素。2.

分区（Partition）：

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

递归排序：

对基准元素左边的子序列和右边的子序列分别递归地进行快速排序。### C++ 代码实现```cpp #include 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];// i 指向小于基准元素的子数组的下一个位置int i = (low - 1);// 遍历 low 到 high-1 的元素for (int j = low; j <= high - 1; j++) {// 如果当前元素小于等于基准元素if (arr[j] <= pivot) {// i 指针右移一位i++;// 交换 arr[i] 和 arr[j]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 arr[], int size) {for (int i = 0; i < size; i++)cout << arr[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 << "排序后的数组: \n";printArray(arr, n);return 0; } ```### 代码解释- `swap()` 函数用于交换两个元素的值。 - `partition()` 函数对数组进行分区操作，选择最后一个元素作为基准元素，并将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边。 - `quickSort()` 函数是快速排序的递归函数，它首先调用 `partition()` 函数对数组进行分区，然后递归地对左右两个子数组进行排序。 - `printArray()` 函数用于打印数组。### 复杂度分析-

时间复杂度：

- 最佳情况：O(n log n)，当每次分区都能将数组分成大小相等的两个子数组时。- 平均情况：O(n log n)- 最坏情况：O(n^2)，当数组已经排好序或逆序时。 -

空间复杂度：

O(log n)，递归调用栈的空间。### 总结快速排序是一种高效的排序算法，在实际应用中被广泛使用。它易于理解和实现，并且在大多数情况下都有着良好的性能。

快速排序算法 C++ 代码

简介快速排序（Quicksort）是一种高效的排序算法，其平均时间复杂度为 O(n log n)。它采用分治策略，将一个序列分成两个子序列，并递归地对子序列进行排序。

算法步骤1. **选择基准元素（Pivot）：** 从序列中选择一个元素作为基准元素，通常选择第一个、最后一个或中间的元素。2. **分区（Partition）：** 将序列中小于基准元素的元素放到基准元素的左边，大于基准元素的元素放到右边。3. **递归排序：** 对基准元素左边的子序列和右边的子序列分别递归地进行快速排序。

C++ 代码实现```cpp

include 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];// i 指向小于基准元素的子数组的下一个位置int i = (low - 1);// 遍历 low 到 high-1 的元素for (int j = low; j <= high - 1; j++) {// 如果当前元素小于等于基准元素if (arr[j] <= pivot) {// i 指针右移一位i++;// 交换 arr[i] 和 arr[j]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 arr[], int size) {for (int i = 0; i < size; i++)cout << arr[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 << "排序后的数组: \n";printArray(arr, n);return 0; } ```

代码解释- `swap()` 函数用于交换两个元素的值。 - `partition()` 函数对数组进行分区操作，选择最后一个元素作为基准元素，并将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边。 - `quickSort()` 函数是快速排序的递归函数，它首先调用 `partition()` 函数对数组进行分区，然后递归地对左右两个子数组进行排序。 - `printArray()` 函数用于打印数组。

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

总结快速排序是一种高效的排序算法，在实际应用中被广泛使用。它易于理解和实现，并且在大多数情况下都有着良好的性能。