请详细介绍快速排序基本思想、适用的场景、以及使用c++语言写出对应代码实现
时间: 2023-06-02 19:06:54 浏览: 56
快速排序基本思想是:选取一个基准值,通过一趟排序将待排记录分隔成独立的两部分,其一部分记录的关键字均比基准值小,另一部分关键字均比基准值大,然后对这两部分记录分别进行快速排序,不断重复该过程,直到所有的记录都排好序为止。
快速排序适用于数据规模比较大的情况,时间复杂度为O(nlogn),具有稳定性。
下面是使用 C 语言实现快速排序的代码:
#include <stdio.h>
void quickSort(int arr[], int left, int right)
{
int i, j, pivot, tmp;
if (left < right) {
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i < right)
i++;
while (arr[j] > arr[pivot])
j--;
if (i < j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
tmp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = tmp;
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
}
int main()
{
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)