「数据结构」八大排序(超详解 附动图 源码)(10)

代码如下：
// 快速排序hoare版本int PartSort1(int* a, int left, int right){ int key = right;//选定基准值 while (left < right) { //选右边为基准值，左指针先走 while (left < right && a[left] <= a[key]) { left ; } //右指针再走 while (left < right && a[right] >= a[key]) { right--; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[key]); return left;}void QuickSort(int* a, int left, int right){ if (left >= right) { return; } int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }

6.2挖坑法

挖坑法与上面的方法类似。
具体思路是：
先将选定的基准值(最左边)直接取出，然后留下一个坑， 当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位， 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位， 重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。
之后也是以基准值为界限，递归排序基准值左右区间。
动图演示：