用C语言编写快速排序
时间: 2023-07-05 11:25:29 浏览: 49
下面是使用C语言实现的快速排序算法代码:
```
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
```
其中,left和right分别表示待排序数组的左右边界。
快速排序的时间复杂度为O(nlogn),是一种高效的排序算法。
相关问题
用c语言编写快速排序
快速排序是一种常用的排序算法,它的时间复杂度为O(nlogn)。下面是用C语言实现快速排序的步骤:
1. 从数列中挑出一个元素作为基准数。
2. 将比基准数小的元素放在基准数左边,比基准数大的元素放在基准数右边。
3. 对左右两个小数列递归地进行步骤1和步骤2,直到各区间只有一个数为止。
下面是一个简单的C语言实现快速排序的代码:
```
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int i = left, j = right, pivot = 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);
}
}
```
这个代码实现了快速排序的基本思路,即通过递归的方式将数组分成左右两个小数组,然后对每个小数组进行排序。在实现过程中,我们需要选择一个基准数,一般选择数组的第一个元素作为基准数。然后我们使用两个指针i和j,分别从数组的左右两端开始扫描,找到第一个比基准数小的数和第一个比基准数大的数,然后交换这两个数的位置。重复这个过程,直到i和j相遇,此时将基准数归位,即将基准数放到i的位置上。最后,我们对基准数左边的小数组和右边的小数组分别进行递归排序即可。
用C语言编写快速排序算法
下面是使用C语言编写快速排序算法的示例代码:
```c
#include<stdio.h>
void quicksort(int *arr, int left, int right) {
if (left < right) {
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);
}
}
int main() {
int arr[] = {8, 2, 7, 5, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
快速排序算法的基本思路是:从数组中选择一个元素作为枢纽元素(pivot),将数组划分为小于pivot的部分和大于pivot的部分。然后对这两部分分别递归调用快速排序算法,直到整个数组有序。这个示例代码中的实现是标准的、原地修改的快速排序算法,其时间复杂度为 O(nlogn)。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](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)