【面试必备】排序算法——快速排序
排序算法是在我们求职面试的时候有很大的概率会被提及，因为不管是在工程类方向中还是在研究类方向中，排序算法的思想都有广泛的应用。
下面，我就来大致的介绍一下各种面试中常见的排序算法的基本思想和相关的实现，希望对你有所帮助。
以下的排序思想都会基于这个序列
21,12,34,67,25,46,52,19来进行讲解，同时配上适当的图解和代码以及代码注释一起讲解。请放心食用。最后的序列都会按照从小到大的顺序进行排列，大家可以自己修改代码，使得序列按照从大到小的顺序排列，以此来检验自己的学习成果。
快速排序
大致思想
快速排序也是一种分治算法。对于一个序列，我们把这个序列划分为两个序列，使得第一个序列的所有的值都小于第二个序列的所有的值。然后对于剩下的两个序列，我们继续进行划分，直到最后划分为n个序列，每个序列只有一个元素。那么这个时候这个序列就是从小到大有序的了。
这里我们先来关注如何将序列划分为两个序列，第一个序列的元素都小于第二个序列的元素。这里，我们可以选择一个枢点，然后经过调整，将序列小于这个枢点的元素都放到左边，否则就放到这个枢点的右边。最后，我们当前要处理的序列就形成了三个部分，比枢点小的序列，枢点，比枢点大的序列（注意，这里不要有一个误解，比枢点小的序列组成的元素不一定是内部有序的，也可能是无序的）。如下图：
执行完了上面这步之后，我们就可以确定序列的一个元素的位置了，就是枢点对应的位置。然后我们递归对左右这两个序列执行同样的处理，直到当前序列只有一个元素了。
至此，我们就实现了整个序列按照从小到大进行排序了。大致的过程如下图：
代码思路分析
- 得到一个初始化的序列A，得到区间的左右端点,.
- 设置当前区间的一个枢点，这里我们默认取当前序列的左端点位置的元素作为初始的枢点，然后经过下面的调整使得成为一个满足枢点左边的元素小于枢点，枢点右边的元素大于枢点的值的序列。记录下枢点的位置，这样我们就可以将这个序列分割为两个序列了，注意这个的位置是固定了的。
- 递归处理和。
- 现在我们来讲解一下在已知枢点和当前序列的左右端点的情况下，如何处理使得满足枢点左边的元素小于枢点，枢点右边的元素大于枢点的值。我们上面说了，这里我们选取的是当前序列的左端这个元素作为枢点的初始值，记为，当前枢点的位置记为。然后，我们遍历当前的序列，如果序列当前的值小于等于，那么就说明这个元素需要放到枢点的左边去,枢点就向右边移动一个位置，，如果i没有跟上序列当前移动的下标，那么就需要将序列位置和位置的值交换，以保证比枢点小的元素在左边。如此执行直到序列遍历完成。最后，将位置i的值和序列的左端点元素的值互换。
代码实现
#include<iostream> #define LEN 8 using namespace std; void print(int a[]){ for(int i=0;i<LEN;i++){ cout<<a[i]<<" "; } cout<<endl; } /** * @brief 划分函数，将序列划分为三个部分，小于枢点的序列，枢点，大于枢点的序列 * * @param a 需要划分的数组 * @param left 数组的左端点下标 * @param right 数组的右端点下标 * @return int 枢点的位置 */ int split(int a[],int left,int right){ int i=left,k=left; int temp=a[left]; for(k=left+1;k<=right;k++){ if(a[k]<=temp){ ++i; if(i!=k){ swap(a[i],a[k]); } } } swap(a[i],a[left]); return i; } /** * @brief 快排函数 * * @param a 需要排序的数组 * @param left 数组的区间左端点 * @param right 数组的区间右端点 */ void quickSort(int a[],int left,int right){ if(left<right){ int pos=split(a,left,right); quickSort(a,left,pos-1); quickSort(a,pos+1,right); } } int main(){ int a[8]={21,12,34,67,25,46,52,19}; quickSort(a,0,LEN-1); print(a); return 0; }复杂度分析
- 空间复杂度
- 这里的空间复杂度主要的消耗时递归调用的，如果每次的枢点都是中点，那么就是最优的空间复杂度,如果每次都是选取的左端点，那么就是最坏的空间复杂度。
- 时间复杂度
- 快排的时间复杂度需要分为最坏情况和平均情况，我们看最坏情况，对于长度为N的序列，如果这个序列初始的时候就是按照从小到大的顺序排列的，那么我们根据代码可以发现我们需要向下递归的次数为N次，每次我们序列的长度减去1，所以总的遍历的次数为.平均复杂度的计算需要假设序列中的所有的元素的关键字都是不同的，元素的每个排列出现的概率都是一样的。那么每个元素被选取作为枢点的概率为，如果被选取的枢点元素经过split之后位于位置，那么左边的元素有个，右边的元素有个。我们设表示对个元素进行排序时所执行的平均比较次数。那么就有
- 空间复杂度
如果这篇帖子对你有用的话，欢迎点赞收藏。你的点赞收藏将是对我最大的鼓励。
近期帖子
春招实习面试经历汇总
面试必问—Redis持久化机制（建议收藏）
互联网话术你知多少？（长期更新中...)
互联网面试算法题题解大合集（强烈建议收藏）
实习经验分享 | 希望可以帮助大家避坑，更早地适应实习生活
牛客回忆录