【hoare优化版】快速排序算法（2）

本文主要是介绍【hoare优化版】快速排序算法（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

GitMidi三数取中

整体思想

图解分析

代码实现

Hoare优化

上篇我们介绍了hoare基础版，但是这种代码存在缺陷，所以我们提出了两种解决方案。主流的解决方案就是【三数取中选key】

GitMidi三数取中

在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数的下标，然后进行排序，将中间数作为枢纽值。

取的三个数的中位数的下标
取的是下标❗
数值两两比较

整体思想

设置三个值下标：begin // end // midi
两个两个比较
得到中位数的下标

图解分析

【顺序序列优化前：等差数列O（N^2)】

【顺序序列优化后：类似二叉树等比数列O（N*logN)】

代码实现

//三数取中
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;if (a[begin] < a[end]){if (a[begin] > a[midi]){return begin;}else if(a[end]<a[midi]){return end;}else{return midi;}}else//begin>=end{if (a[midi] < a[end]){return end;}else if (a[midi] > a[begin]){return begin;}else{return midi;}}
}

Hoare优化

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;if (a[begin] < a[end]){if (a[begin] > a[midi]){return begin;}else if(a[end]<a[midi]){return end;}else{return midi;}}else//begin>=end{if (a[midi] < a[end]){return end;}else if (a[midi] > a[begin]){return begin;}else{return midi;}}
}//优化版本
int PartSort1(int* a, int begin, int end)//返回分割线
{int left = begin;int right = end;int keyi = begin;//三数取中int midi = GetMidi(a, begin, end);Swap(&a[keyi], &a[midi]);while (left < right){//找小while (left < right && a[right] >= a[keyi]){right--;}//找大while (left < right && a[left] <= a[keyi]){left++;}//找到了Swap(&a[right], &a[left]);}Swap(&a[left], &a[keyi]);keyi = left;return keyi;//分割 [begin,keyi-1] keyi [keyi+1,end]
}void QuickSort(int* a, int begin,int end)
{if (begin >= end)//只有1个元素 没有区间{return;}int keyi = PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}