用C++实现一个快速排序
时间: 2023-02-08 13:55:22 浏览: 189
下面是一个用 C 语言实现的快速排序算法的代码示例:
```
#include <stdio.h>
void quick_sort(int array[], int start, int end)
{
if (start >= end)
return;
int pivot = array[end];
int partition_index = start;
for (int i = start; i < end; i++)
if (array[i] < pivot) {
int temp = array[i];
array[i] = array[partition_index];
array[partition_index] = temp;
partition_index++;
}
array[end] = array[partition_index];
array[partition_index] = pivot;
quick_sort(array, start, partition_index - 1);
quick_sort(array, partition_index + 1, end);
}
int main(void)
{
int array[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
int size = sizeof(array) / sizeof(array[0]);
quick_sort(array, 0, size - 1);
for (int i = 0; i < size; i++)
printf("%d ", array[i]);
return 0;
}
```
这段代码的输出将会是:
```
0 1 2 3 4 5 6 7 8 9
```
快速排序的基本思想是:
1. 在数列中选择一个元素作为基准(pivot)
2. 把比基准小的元素移到基准左边,把比基准大的元素移到基准右边
3. 对基准左右两边的子序列分别重复步骤 1 和 2,直到所有元素都有序
快速排序是一种分治算法,它的时间复杂度在最坏情况下是 O(n^2),但平均情况下是 O(nlogn),因此它是一种非常有效的排序算法。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)