快排补充（挖坑法，lomuto前后指针，非递归法）

挖坑法

挖坑法方法分析

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）。注意这里用的是lift<right此处的和快排的有区别，具体的情况需要根据实际情况进行区分。

源代码

int _QuickSort(int* arr, int left, int right)
{int hole = left;int base = arr[hole];while (left < right){while (left < right && arr[right] > base){right--;}arr[hole]=arr[right];hole = right;while (left < right && arr[left] < base){left++;}arr[hole] = arr[left];hole = left;}//此时已经不满足，left<=right这时候把hole和关键值进行置换arr[hole] = base;return hole;
}

lomuto前后指针

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

前后指针方法分析

思路：定义两个变量prev和cru这两个指针，用cur指向的位置与key的值进行对比，具体具有以下两者情况。

若arr[cru]<arr[key]，pre向后移动，并把pre所指向的值与cru的值进行交换。

若arr[cru]>=arr[key]，cru向继续后移动，当小于时再进行pre的后移动，并把pre所指向的值与cru的值进行交换。

前后指针方法的缺点

arr[cur]<arr[base]？

arr[cur]<=arr[base]？

在这这两种情况下我们可以看出不论是小于等于还是小于，其实都会分成不均匀的两部分，这样会使后面递归调用的时间复杂较差。遇见相同元素的序列时使用前后指针效果较差，但是总体来说先后指针的思路和代码还是很好用的。

源代码

int _QuickSort(int* arr, int left, int right)
{int base = left;int prev = left;int cur = left + 1;while (cur<=right){if( arr[cur]<arr[base]&& (++prev)!=cur){swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[base], &arr[prev]);return prev;
}

非递归法

非递归法方法分析

找关键值的方法并未改变，可以使用（hoare，挖坑法，快慢指针）这三种方法。
根据基准值划分左右区间，左区间：[begin,keyi-1]，右区间：[keyi+1,end]。两个注意点当区间的左侧大于右侧，或者左右两侧是一个相同的树就不在入栈了。
借助栈使用栈的循环模拟实现递归的功能。这里要注意入栈是先进后出，所以先right再入left。
循环到栈为空为止。

非递归的优点

避免栈溢出：递归调用函数可能会导致栈溢出，特别是在处理大规模数据时。使用非递归的方式可以避免这种情况的发生。
更容易实现：非递归的快速排序实现相对简单，不需要考虑递归调用的细节，也不需要处理递归栈的问题。
更容易优化：非递归的快速排序可以更容易地进行优化，例如使用迭代代替递归、使用栈来存储待处理的子数组等。

源代码

void swap(int* n, int* m)
{int temp = *n;*n = *m;*m = temp;
}
void QuickSortNonR(int* arr, int left, int right)
{ST st;StInit(&st);StPush(&st, right);StPush(&st, left);while (!StEmpty(&st)){//取栈顶元素---取两次int begin = StTop(&st);StPop(&st);int end = StTop(&st);StPop(&st);//[begin,end]---找基准值int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);keyi = prev;//根据基准值划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]//当左边大于右边或者值相同不入栈if (keyi + 1 < end){StPush(&st, end);StPush(&st, keyi + 1);}if (keyi - 1 > begin){StPush(&st, keyi - 1);StPush(&st, begin);}}StDestory(&st);
}