排序算法在我们校招考察中很常见，所以今天咋也对很常见的快速排序做出总结，希望能够帮助朋友们理解！

一：快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

二：基本框架

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来。

三：单趟逻辑

选出一个基准值，一般是第一个数或者是最后一个数，经过单趟排序后的结果是左边的值都比基准值小，右边的值都比基准值大。
将区间按照基准值划分为左右两半部分的常见方式有：

3.1：hoare版本

动图演示：

💡💡💡思想：从右边开始找比基准值小的值，从左边找比基准值大的值，等都找到时，交换，再继续上述过程，相遇以后，再把相遇位置的值跟基准值做交换！

int hoare(vector<int>& v, int left, int right)
{int keyi = left;while (left < right){while (left < right && v[right] >= v[keyi]){right--;}while (left < right && v[left] <= v[keyi]){left++;}swap(v[left], v[right]);}swap(v[keyi], v[left]);return left;
}
void QuickSort(vector<int>& v, int left, int right)
{//双闭区间if (left >= right){return;}int div = hoare(v, left, right);QuickSort(v, left, div - 1);QuickSort(v, div + 1, right);
}

💡💡思考：如何保证相遇的位置一定比基准值小呢？

• 如果选第一个数作为基准值，那么让右边先走，可以保证。
• 如果选最后一个数作为基准值，那么让左边先走，可以保证。

3.2：挖坑法

先将第一个数据存放在临时变量中，形成一个坑位，比如说找最左边的值作为key，形成一个坑位，那么从右边先走，找比key值更小的值，找到之后把该值放到坑位，形成新的坑位，又从左边找新的比key值大的值放到坑位，依次循环，相遇的位置一定在坑上，再把key值放到坑上。
动图演示：

代码示例：

int DigPit(vector<int>& v, int left, int right)
{int key = v[left];while (left < right){while (left < right && v[right] >= key){right--;}v[left] = v[right];while (left < right && v[left] <= key){left++;}v[right] = v[left];}v[left] = key;return left;
}
void QuickSort(vector<int>& v, int left, int right)
{//双闭区间if (left >= right){return;}int div = DigPit(v, left, right);QuickSort(v, left, div - 1);QuickSort(v, div + 1, right);
}

相比于版本一的好处在于：

• 不需要去理解为什么左边做基准值时，要让右边先走。
• 相遇位置一定在坑位上，再把基准值扔到坑位上。

3.3：前后指针法

初始时，选取第一个值作为基准值，prev指针指向序列开头，cur指针指向prev指针的后一个位置，然后cur指针一直向后找比基准值小的值，找到后，先把prev指针向后移动一位，再交换prev和cur位置的值，最后当cur越界结束，再把prev处的值与序列开头值交换。

int QSPtr(vector<int>& v, int left, int right)
{int key = v[left];int prev = left;int cur = left + 1;while (cur <= right){if (v[cur] < key && v[prev] != v[cur]){prev++;swap(v[cur], v[prev]);}cur++;}swap(v[prev], v[left]);return prev;
}
void QuickSort(vector<int>& v, int left, int right)
{//双闭区间if (left >= right){return;}int div = QSPtr(v, left, right);QuickSort(v, left, div - 1);QuickSort(v, div + 1, right);
}

注意到prev指针和cur指针中间间隔的是一段比基准值大的区间！

四：快速排序的优化

• 我们首先思考快速排序的最优情况是什么？

那就是每次选出的key值都大致单趟排序后位于序列中部，那么这时时间复杂度就是n*logn。

• 其实思考快速排序的最坏情况是什么？
  那就是每次取出的key值都是序列中的最大值或者最小值，此时时间复杂度就是o(n^2)。

所以我们提出一种优化策略，那就是每次取出的数字都是大致是中位数！

💡💡💡首先

• 三数取中法选key。

int GetmidIndex(vector<int>& v, int left, int right){int mid = (left + right) / 2;//left + (right - left) / 2;if (v[left] < v[mid]){if (v[mid] < v[right]){return mid;}else if (v[left] > v[right]){return left;}else{return right;}}else{if (v[mid] > v[right]){return mid;}else if (v[left] > v[right]){return right;}else{return left;}}
}int QSPtr(vector<int>& v, int left, int right)
{int midi = GetmidIndex(v, left, right);swap(v[left], v[midi]);//以下步骤都是一样int key = v[left];int prev = left;int cur = left + 1;while (cur <= right){if (v[cur] < key && v[prev] != v[cur]){prev++;swap(v[cur], v[prev]);}cur++;}swap(v[prev], v[left]);return prev;
}void QuickSort(vector<int>& v, int left, int right)
{//双闭区间if (left >= right){return;}int div = QSPtr(v, left, right);QuickSort(v, left, div - 1);QuickSort(v, div + 1, right);
}

💡💡💡其次

• 小区间优化，递归到小的子区间时，可以考虑使用插入排序。

void QuickSort(vector<int>& v, int left, int right)
{//双闭区间if (left >= right){return;}if (right - left < 10){//插入排序}int div = QSPtr(v, left, right);QuickSort(v, left, div - 1);QuickSort(v, div + 1, right);
}

当区间很小时，不再使用递归划分的思想让他有序，而是直接使用插入排序对小区间排序，减少递归调用。（我们知道插入排序在小区间大致有序的情况下效率是比较高的）。

五：快速排序的非递归实现（非常重要）

void NonQuickSort(vector<int>& v)
{int left = 0, right = v.size() - 1;stack<int> st;st.push(left);st.push(right);while (!st.empty()){int right = st.top();st.pop();int left = st.top();st.pop();int div = DigPit(v, left, right);if (div - 1 > left)//说明该区间至少两个元素{st.push(left);st.push(div - 1);}if (right - 1 > div){st.push(div + 1);st.push(right);}}
}
int main()
{vector<int> v = { 2, 1, 4, 3, 4, 9, 8, 7, 0 };NonQuickSort(v);for (auto e : v){cout << e << " ";}cout << endl;system("pause");return 0;
}

六：快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

火车头插件