前面我们已经了解了几大排序了，那么我们今天就来再了解一下剩下的快速排序法，这是一种非常经典的方法，时间复杂度是N*logN。

快速排序法：

基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

我们的快速排序可以通过递归和非递归来实现，我们先来看看递归实现快排，我们的递归快排又分为三个版本，三种方法各有各的特点，我们接下来就来看看吧。

需要调用的函数代码：

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;// begin midi end 三个数选中位数if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else // a[begin] > a[midi]{if (a[midi] > a[end])return midi;else if (a[begin] < a[end])return begin;elsereturn end;}
}

hoare版本单趟排序：

// hoare
int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}

这个版本的单趟排序理解起来很容易，但是我们的坑点比较多，所以难度对于我们而言还是有点挑战性，我们需要两个变量来实现，我们的left从左边数组的首元素开始走，找比keyi位置大的元素，keyi代表的就是我们数组首元素的下标，我们用right从最后一个元素开始走，找比keyi位置小的元素，找到了一个大的元素和一个小的元素就交换，但是我们的数组中可能有多个相等的元素，所以我们内嵌循环就得用<=。我们最后left和right相遇时结束，相遇位置的右边的元素大于等于keyi位置的元素，而相遇位置左边的元素都小于等于keyi位置的元素，我们最后就将left位置的元素和keyi位置的元素交换再返回left就完成了。

挖坑法单趟排序：

int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小，填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大，填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}

我们先将第一个数据存放在临时变量key中形成一个坑位，我们同样用到left和right，同样的用法，left从第一个元素往后走，right从最后一个元素往前走。我们的right先走，找到一个比hole下标小的元素就于hole下标的元素交换，交换之后left再走，找到一个比hole位置大的元素就与hole位置的元素交换，然后再left位置形成一个坑点。然后又是right走，交换后left走，反复进行，最后在相遇的时候就结束循环。因为我们的hole下标的值都是空的，所以在最后我们将key的数据给hole下标的坑位就可以了，最后再返回坑位的数据。具体的过程如下图所示：

前后指针版本单趟排序：

int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

我们的前后指针版本看起来比前两个版本更加的容易，因为我们的两个指针prev指向我们数组首元素的下标，而cur是我们首元素的下一个元素的下标，我们的cur先走，如果我们指向的元素比keyi位置的元素大的话我们就cur++向前走一位，如果比keyi位置的元素小的话我们就prev++向前走一位再与cur位置的交换，cur再继续往前走知道cur>end的时候就结束循环。最后我们再将prev位置的数据给keyi位置就完成了。

单趟优化版本：

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

单趟优化版本就是我们的区间数据不大时，我们用直接插入排序法，而数据太大的时候我们就用hoare版本的单趟排序。

函数递归实现快排：

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

实现我们只需要调用一个版本的单趟排序在进行递归就可以了。我们代码中是用的挖坑法的单趟排序，我们就直接调用PartSort2就可以了。

递归的我们已经了解完了，那么我们就来看看非递归的怎么实现吧：

void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}

非递归版本的快速排序。我们需要起始位置 begin 和结束位置 end。首先，函数创建一个栈 st，用于存储待处理的子数组的起始和结束位置。将 end 和 begin 分别压入栈中，表示对整个数组进行排序。进入循环，只要栈不为空，从栈中弹出两个元素，分别赋值给 left 和 right，表示当前要处理的子数组的起始和结束位置。调用 PartSort3 函数对子数组进行分区，得到基准元素的位置 keyi。根据分区的结果，将子数组划分为 [left, keyi-1]、[keyi]、[keyi+1, right] 三个部分。如果 keyi + 1 < right，说明右侧子数组仍然有元素需要排序，将右侧子数组的起始位置 keyi + 1 和结束位置 right 压入栈中。如果 left < keyi - 1，说明左侧子数组仍然有元素需要排序，将左侧子数组的起始位置 left 和结束位置 keyi - 1 压入栈中。循环继续进行，直到栈为空，表示所有子数组都被处理完毕。最后，销毁栈 st，就完成了非递归版本的快速排序。

如果对大家有所帮助的话就支持一下吧！