一、什么是挖坑法？
挖坑法的思想是：先保存最左边的left位置的key值，然后最左边的left位置就可以看作是一个“坑”，因为它可以被其他数据覆盖（key已经被保存起来，所以不用担心原来的数据被覆盖掉），然后先从右边right位置开始往左找比key小的数，找到后把这个值填到“坑”里面，那么这个位置就会变成一个新的“坑”，再从左边left位置开始往右找比key大的数，找到后又把它填到“坑”里面，再从右向左找比key小的，以此类推，最后它们一定会在坑里相遇，因为left和right肯定有一个为“坑”，最后把刚开始保存的key值填到这个“坑”里就完成了一趟的快速排序。这个坑的位置也就是hoare版本返回的keyi，以这个坑为分界线，递归对左边的子数组和右边的子数组以同样的方式做快速排序，直到子区间只有一个值（left==right）或者子区间不存在（left>right）的时候就不用再递归下去了。最终就能完成对整个数组的排序。
hoare版本的快排：https://blog.csdn.net/weixin_70056514/article/details/129969288?spm=1001.2014.3001.5502
其实这个挖坑法是有人在基于hoare版本的快排的基础上，对其进行的一个排序的实现方式的改版而已，因为有人觉得hoare版本的快速排序在选key的时候要遵循“左边做key，右边先走”的原则，这个地方也是很多人不太容易理解的地方，很多人都想不明白这是为什么，不太好理解，所以就会记不住，可能有一天写的时候就不记得是左边先走还是右边先走了，容易出错。但是这个挖坑法就很好理解了，因为选左边做key，那么刚开始“坑”就在左边，那自然就是先从right往左找比key小的，然后填到左边这个坑里，形成新“坑”，再从left往右找比key大的填到坑里，以此类推，这样就不会出错了。但是这个挖坑法的本质还是和hoare版本的快排是一样的，只不过实现的方式不同。
二、如何实现挖坑法？
动图演示如下：
参考代码：
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } //三数取中 int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) { return mid; } //来到这里证明a[mid]最小，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } else//a[left]<=a[mid] { if (a[mid] < a[right]) { return mid; } //来到这里证明a[mid]最大，那么a[left]和a[right] //谁小谁就是中间的那个数 else if (a[left] < a[right]) { return left; } else { return right; } } } //直接插入排序（快排需要小区间优化） void InsertSort(int* a, int n) { assert(a); int i = 0; int end = 0; int tmp = 0; for (i = 0; i < n - 1; i++) { end = i; tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } } // 快速排序挖坑法 int PartSort2(int* a, int left, int right) { //三数取中 int mid = GetMidNumi(a, left, right); if (mid != left) { Swap(&a[mid], &a[left]); } //先保存最左边的作为key int key = a[left]; //让最左边的位置作为坑 int pit = left; while (left < right) { //右边找小 while (left < right && a[right] >= key) { --right; } //找到比key小的就填到坑里 a[pit] = a[right]; //让right变为新的坑 pit = right; //左边找大 while (left < right && a[left] <= key) { ++left; } //左边找到比key大的就填到右边的坑里 a[pit] = a[left]; //让left位置变为新的坑 pit = left; } //最后把key填到坑里面（即相遇的位置） a[pit] = key; //返回坑的位置作为下一次递归排序的分界点 return pit; } void QuickSort(int* a, int left,int right) { assert(a); //区间只有一个值或者区间不存在就不用再递归下去了 if (left >= right) { return; } //这里进行一个小区间优化，当一个区间<=10个元素的时候 //快排已经不再适合，因为快排是数据越多并且越乱的时候 //才是越快的，但是数据量小的时候，快排是没有很大的优势 // 的如果这个是一个大数组经过多次递归下来的小区间，证明 // 这个区间接近于有序的，此时换成直接插入排序会更加的高效 if (right - left + 1 < 10) { InsertSort(a + left, right + 1 - left); } else { //每一趟快排之后都返回keyi的位置，把区间分成 //[left,keyi-1][keyi][keyi+1,right]三个部分 //再对子区间的数组进行快排，直到不满足递归条件再返回 int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }
三、挖坑法的时间复杂度是多少？
这个挖坑法的时间复杂度也是O(N*logN)，证明如下：
