看完这个，你觉得你真的懂快速排序吗？ _排序

看似青铜实则王者很多人提起快排和二分都觉得很容易的样子，但是让现场Code很多就翻车了，就算可以写出个递归版本的代码，但是对其中的复杂度分析、边界条件的考虑、非递归改造、代码优化等就无从下手，填鸭背诵基本上分分钟就被面试官摆平了。

文章插图

那年初识快速排序

快速排序Quicksort又称划分交换排序partition-exchange sort ，简称快排，一种排序算法。最早由东尼·霍尔(C. A. R. Hoare)教授在1960年左右提出，在平均状况下，排序n个项目要O(nlogn)次比较。
在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

快速排序的核心思想在计算机科学中，分治法(Divide&Conquer)是建基于多项分支递归的一种很重要的算法范式，快速排序是分治思想在排序问题上的典型应用。
所谓分治思想D&C就是把一个较大规模的问题拆分为若干小规模且相似的问题。再对小规模问题进行求解，最终合并所有小问题的解，从而形成原来大规模问题的解。
字面上的解释是"分而治之" ，这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。
分治法中最重要的部分是循环递归的过程，每一层递归有三个具体步骤：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
合并：将各子问题的解合并为原问题的解。

快速排序的基本过程
快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。
递归地排序两个子序列，直至最小的子序列长度为0或者1 ，整个递归过程结束，详细步骤为：

挑选基准值: 从数列中挑出一个元素称为基准pivot ，选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
基准值分割: 重新排序数列，所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面，与基准值相等的数可以到任何一边,在这个分割结束之后，对基准值的排序就已经完成。
递归子序列: 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序，步骤同上两步骤,递归终止条件是序列大小是0或1 ，因为此时该数列显然已经有序。

快速排序的递归实现

版本一 C实现

#include<stdio.h>int a[9]={5,1,9,6,7,11,3,8,4};void exchange(int *p,int *q){ int temp=*p; *p=*q; *q=temp;}int quicksort(int left,int right){ if(left>=right){ return 0; } int i,j,temp; temp=a[left]; i=left; j=right; while(i!=j){ while(i<j&&a[j]>=temp){ j--; } exchange(&a[i],&a[j]);while(i<j&&a[i]<=temp){ i++;} exchange(&a[i],&a[j]); } quicksort(i+1,right); quicksort(left,i-1); }int main(){ quicksort(0,8); for(int i=0;i<=8;i++){ printf("%d ",a[i]); }}

版本二 C++实现

#include<IOStream>using namespace std;template <typename T>void quick_sort_recursive(T arr[], int start, int end) { if (start >= end) return; T mid = arr[end]; int left = start, right = end - 1; //整个范围内搜寻比枢纽值小或大的元素，然后左侧元素与右侧元素交换 while (left < right) { //试图在左侧找到一个比枢纽元更大的元素 while (arr[left] < mid && left < right) left++; //试图在右侧找到一个比枢纽元更小的元素 while (arr[right] >= mid && left < right) right--; //交换元素 std::swap(arr[left], arr[right]); } //这一步很关键 if (arr[left] >= arr[end]) std::swap(arr[left], arr[end]); else left++; quick_sort_recursive(arr, start, left - 1); quick_sort_recursive(arr, left + 1, end);}//模板化template <typename T> void quick_sort(T arr[], int len) { quick_sort_recursive(arr, 0, len - 1);}int main(){ int a[9]={5,1,9,6,7,11,3,8,4}; int len = sizeof(a)/sizeof(int); quick_sort(a,len-1); for(int i=0;i<len-1;i++) cout<<a[i]<<endl;}两个版本均可正确运行，但代码有一点差异: