用C语言写快速排序并解释
时间: 2023-12-12 09:30:23 浏览: 29
快速排序(Quicksort)是一种常见的排序算法,它采用了分治策略。
具体来说,快速排序的过程如下:
1. 选取一个基准元素(pivot);
2. 遍历数组,将小于等于基准元素的元素放在基准元素左边,大于基准元素的元素放在基准元素右边;
3. 对基准元素左右两个子数组分别递归进行快速排序。
以下是用C语言实现快速排序的代码:
```
void quick_sort(int arr[], int left, int right) {
if (left >= right) {
return; // 当左指针大于或等于右指针时,停止递归
}
int i = left, j = right, pivot = arr[left]; // 选取arr[left]为基准元素
while (i < j) {
while (i < j && arr[j] > pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot; // 将基准元素放到正确的位置上
quick_sort(arr, left, i - 1); // 递归快排左边的子数组
quick_sort(arr, i + 1, right); // 递归快排右边的子数组
}
```
这段代码中,left和right分别表示当前需要排序的子数组的左右边界。pivot是选取的基准元素。i和j分别表示左右两个指针。
快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn)。它是一种原地排序算法,不需要额外的存储空间。在实际应用中,快速排序的效率非常高,被广泛使用。
相关推荐
![text/plain](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)
![](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)