快速排序三者取中法c++
时间: 2023-09-23 09:12:58 浏览: 75
三数取中法是一种改进的快速排序算法中的一种优化方法。该方法通过在待排序数组的左端、右端和中间选择三个元素,并将这三个元素进行排序,将中间值作为枢纽元(pivot)来进行分割。这样可以尽量避免在有序数组中选择极值作为枢轴,从而提高快速排序的效率。
下面是一种C语言实现的快速排序三数取中法的代码示例:
```c
#include <stdio.h>
void Swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void InsertionSort(int *arr, int left, int right) {
for(int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while(j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int Median3(int *arr, int left, int right) {
int center = (left + right) / 2;
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]);
}
Swap(&arr[center], &arr[right - 1]);
return arr[right - 1];}
void QuickSort(int *arr, int left, int right) {
const int Cutoff = 5; // 当待排序的元素个数小于等于Cutoff时,使用插入排序
if(left + Cutoff <= right) {
int pivot = Median3(arr, left, right);
int i = left;
int j = right - 1;
while(1) {
while(arr[++i] < pivot);
while(arr[--j] > pivot);
if(i < j) {
Swap(&arr[i], &arr[j]);
}
else {
break;
}
}
Swap(&arr[i], &arr[right - 1]); // 将枢轴放到正确的位置
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
}
else {
InsertionSort(arr, left, right);
}
}
int main() {
int arr[] = {5, 2, 1, 4, 3, 6, 9, 8, 7, 0};
QuickSort(arr, 0, 9);
for(int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)