使用C语言,三数取中法来实现快速排序算法
时间: 2023-07-07 20:25:19 浏览: 60
好的,下面是使用C语言,三数取中法来实现快速排序算法的代码:
```
#include <stdio.h>
/* 交换两个数的位置 */
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/* 三数取中法选取枢纽元 */
int median(int arr[], int left, int right) {
int center = (left + right) / 2;
/* 保证 left <= center <= right */
if (arr[left] > arr[center])
swap(&arr[left], &arr[center]);
if (arr[left] > arr[right])
swap(&arr[left], &arr[right]);
if (arr[center] > arr[right])
swap(&arr[center], &arr[right]);
/* 将 center 放到 right - 1 的位置 */
swap(&arr[center], &arr[right - 1]);
/* 返回枢纽元的值 */
return arr[right - 1];
}
/* 快速排序 */
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int i = left, j = right - 1;
int pivot = median(arr, left, right); /* 选取枢纽元 */
while (1) {
/* 从左往右找到第一个大于枢纽元的数 */
while (arr[++i] < pivot) {}
/* 从右往左找到第一个小于枢纽元的数 */
while (arr[--j] > pivot) {}
if (i < j) {
/* 将左边的数与右边的数交换 */
swap(&arr[i], &arr[j]);
} else {
/* 结束循环 */
break;
}
}
/* 将枢纽元与 i 所在位置的数交换 */
swap(&arr[i], &arr[right - 1]);
/* 对左边的子数组进行快速排序 */
quick_sort(arr, left, i - 1);
/* 对右边的子数组进行快速排序 */
quick_sort(arr, i + 1, right);
}
}
int main() {
int arr[] = {6, 2, 5, 4, 3, 1};
int len = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, 0, len - 1);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
在这个实现中,我们使用了三数取中法来选取枢纽元,这可以有效地避免最坏情况的发生,提高快速排序的效率。此外,我们还实现了一个 `swap` 函数来交换两个数的位置。最后,我们在 `main` 函数中定义了一个待排序的数组,并且调用 `quick_sort` 函数对其进行排序。
相关推荐
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)