快速排序【hoare】--附图示以及代码

霍尔快速排序Hoare’s Quicksort详细介绍一、核心思想利用分治思想通过单趟排序把数组a划分成左右两段左段所有元素 ≤ 枢轴值a[keyi]右段所有元素 ≥ 枢轴值a[keyi]递归地对左右段做同样的处理最终完成整个数组的排序。1.1 算法步骤选枢轴三数取中拿到中值索引与a[left]交换后固定keyi left以a[keyi]为基准。分区用left、right两个指针相向扫描右边找a[right] a[keyi]左边找a[left] a[keyi]找到后swap交换直到left和right相遇最后swap(a[keyi], a[meeti])将枢轴放到正确位置返回meeti递归排序对[left_initial, meeti-1]和[meeti1, right_initial]两个子区间重复上述过程直到区间长度 ≤ 1。1.2 霍尔分区的详细步骤分区准备当前待分区的区间为[left, right]。为减少最坏情况出现的概率代码已使用三数取中法选出中值元素并将其交换到a[left]位置。此后以a[keyi]作为基准值枢轴其中keyi left。指针初始化右指针right初始指向区间右端点左指针left初始指向区间左端点。循环扫描与交换在left right的条件下反复执行以下流程右指针right不断向左移动自减直到找到第一个严格小于基准值的元素即a[right] a[keyi]。移动过程中始终保证left right。左指针left不断向右移动自增直到找到第一个严格大于基准值的元素即a[left] a[keyi]。移动过程中始终保证left right。如果此时仍然满足left right说明左右各找到了需要交换的元素于是交换a[left]和a[right]然后继续下一轮扫描。若left right说明指针已经相遇或交错扫描阶段结束。循环不变量在扫描的全过程中始终成立指针left左侧不含left本身的所有元素均 ≤a[keyi]指针right右侧不含right本身的所有元素均 ≥a[keyi]。分区完成当左右指针相遇或交错后记相遇位置为meeti left此时有left right。最后执行一次交换swap(a[keyi], a[meeti])将基准值放入它在完全排序后的正确位置。函数最终返回meeti。此时数组被划分为三个部分a[left_initial … meeti-1]元素全部 ≤ 基准值a[meeti]基准值本身已处于正确排序位置a[meeti1 … right_initial]元素全部 ≥ 基准值。二、动图演示三、快速排序的复杂度与稳定性分析时间复杂度快速排序的时间复杂度取决于每次分区操作的平衡程度与数据分布密切相关。最好情况O(n log n)当每次选择的基准值枢轴都能将数组均匀划分为两个大小相近的子区间时递归深度为 log n每层比较次数为 O(n)总复杂度为 O(n log n)。最坏情况O(n²)当每次选择的基准值都是当前区间的最小值或最大值例如数组已有序且未做任何优化时每次分区只划分出一个空区间和一个大小为 n-1 的区间递归深度变为 n每层比较次数为 O(n)总复杂度退化为 O(n²)。通过随机选择基准或三数取中法可大幅降低最坏情况出现的概率。平均情况O(n log n)在随机数据下基准值落在区间中部附近的概率较高递归树趋于平衡数学期望为 O(n log n)。快速排序在实际应用中通常表现优异常数因子较小。空间复杂度快速排序的空间消耗主要来自递归调用栈辅助空间为 O(1)原地分区。递归栈深度平均情况下递归深度为 O(log n)因此空间复杂度为O(log n)。最坏情况下极端不平衡递归深度为 O(n)空间复杂度退化为O(n)。辅助数组无需额外数组所有交换在原数组上完成额外空间仅用于几个临时变量为 O(1)。若采用尾递归优化或迭代实现可将栈空间进一步降低但最坏情况仍可能达到 O(n)。稳定性快速排序是一种不稳定的排序算法。原因在分区过程中元素通过交换swap移动位置相同的元素可能因为基准值的移动而改变相对顺序。示例数组[2a, 1, 2b]两个相等的 2 分别标记为 a、b若基准值为 1则分区后2b可能被换到2a前面导致相对顺序变化。若需保持稳定性可选择归并排序或插入排序等稳定算法。四、示例代码#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includeassert.h//交换voidswap(int*p1,int*p2){inttemp*p1;*p1*p2;*p2temp;}//三数取中intGetMidIndex(int*a,intleft,intright){intmidleft(right-left)/2;if(a[left]a[mid]){if(a[mid]a[right]){returnmid;}elseif(a[left]a[right]){returnleft;}elsereturnright;}else// a[left] a[mid]{if(a[mid]a[right]){returnmid;}elseif(a[left]a[right]){returnleft;}elsereturnright;}}//hoare法intPartSort1(int*a,intleft,intright){intmidGetMidIndex(a,left,right);swap(a[left],a[mid]);intkeyileft;while(leftright){while(leftrighta[right]a[keyi]){right--;}while(leftrighta[left]a[keyi]){left;}if(leftright){swap(a[right],a[left]);}}intmeetleft;swap(a[keyi],a[meet]);returnmeet;}intmain(){intarr[]{6,1,2,7,9,3,4,5,10,8};intnsizeof(arr)/sizeof(arr[0]);intleft0;intrightn-1;QuickSort(arr,left,right);for(inti0;in;i){printf(%d ,arr[i]);}return0;}