快排优化（三数取中法）
前言
作为刚刚入门c和c++的小菜鸡，心血来潮决定写点学习笔记，希望大家提出改进意见。另建议先看代码在看解析。
提示：以下是本篇文章正文内容
一、三数取中法
取所选数组中最左，中间和最右的数组元素进行比较，取中间值作为基准数，先将基准数放在数组最右端，然后比基准数小的放在其左（下简称左数组），比基准数大的放在其右（下简称右数组）。
以「9，2，2，7，6，8」为例
基准数为a[5]=8，第一次快排得到的结果为
6，2，2，7，8，9
do-while循环中得到6，2，2，7，9，8
（此时left=right=4）
将left（right）与基准数交换得到结果。
二、递归思想
进行第一次快排后，分别对左数组和右数组再次进行快排（此时由于左数组和右数组的数组元素个数可能差距过大，可自行调整优化）
三、程序实现过程（代码）
1.取基准数（三数取中）
代码如下（示例）：
void partition(int *arr, int left, int right){
int mid = (left+right)>>1;
int t1 = arr[left], t2 = arr[mid], t3 = arr[right];
if((t1 <= t2 && t2 <= t3) || (t3 <= t2 && t2 <= t1))
swap(arr[right], arr[mid]);
else if((t2 <= t1 && t1 <= t3) || (t3 <= t1 && t1 <=t2))
swap(arr[right], arr[left]);
}
2.快速排序（递归）
代码如下（示例）：
void quickSort(int *arr,int l,int r){
if (l >= r){
return ;
}
int n = r-l+1;
partition(arr,l,r);
int pivot = arr[r];
do
{
while(l<r && arr[l]<=pivot) l++;
while(l<r && arr[r]>=pivot) r--;
if(l < r)
swap(arr[l], arr[r]);
}while(l < r);
arr[n-1] = arr[l];
arr[l] = pivot;
quickSort(arr, 0 , l-1);
quickSort(arr, l+1 , n-1);
}
总结
三数取中法yyds！
|