快速排序是一种常见的排序算法，也是面试中面试官很喜欢考察的一种算法，据不完全统计，24秋招面试中，快手，美团，百度，腾讯，米哈游等多家互联网公司都对这个算法进行了不止一次的考察，是一道面试中出现频率很高的一道算法题。这里给大家一张总结图，是对应十大排序算法的一个复杂度和稳定性的说明，供大家参考算法讲解快速排序（Quick Sort）是一种常用的排序算法，它是一种分治法的应用。该算法的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有元素都比另一部分小，然后再按此方法对这两部分数据分别进行快速排序，整个过程递归进行，直到整个序列有序。算法步骤首先，我们考虑对下面的数组进行快速排序1.选择基准数字我们选取数组的中间元素7为基准数，按照快速排序算法的思想，我们需要把数组分成两部分：左边的部分中的所有元素≤7，右边的部分中的所有元素≥7 我们可以定义两个指针i和j分别指向数组中的第一个元素的位置和最后一个元素的位置，部分代码如下所示public static void quickSort(int[] q, int l, int r){ int x = q[l + r >> 1], i = l - 1, j = r + 1;}这里为什么会让i和j分别指向l-1和r+1呢，这里其实是做了一些技巧性的优化，防止代码出现死循环，这个放在后面展示完整代码的时候会进一步说明，后面分析还是会按照指向l和r来分析，也就是对应的数组中的第一个元素的位置和最后一个元素的位置。2.分割数组将数组中比基准元素小的元素移到基准元素的左边，比基准元素大的元素移到右边。 我们对上面给定的这个例子来模拟这个过程第一步：对于指针，需要跳过所有<基准元素7的数字，最终停在第一个，也就是元素8的位置while( q[++i] < x );第二步：对于指针，需要跳过所有>基准数字7的数字，最终停在第一个，也就是元素6的位置while( q[--j] > x) ;第三步：判断当前指针的位置是否小于指针的位置，如果满足该条件，则交换指针和指针的指向的元素，并重复上述过程，直到不满足上述条件if(i < j){    int t = q[i];    q[i] = q[j];    q[j] = t;}重复上述过程之后，我们可以将原数组排列成其中指针i和指针j的指向会出现图中的这种情况，是因为while循环中是先移动，在判断，因此就会出现的情况，这个过程的完整代码如下所示        while(i < j){            while( q[++i] < x );            while( q[--j] > x) ;            if(i < j){                int t = q[i];                q[i] = q[j];                q[j] = t;            }        }3.递归子数组至此，我们将整个数组一分为2，分成了两个部分，左边部分的范围为,左边范围中所有的元素均<7，右边部分的范围为，右边范围中所有元素均，那么我们可以对左右两边递归执行上述步骤1选择基数数字和步骤2分割数组，直到遇到数组不可分的情况(数组长度=1)，这个时候递归就结束了。        quickSort(q, l, j);        quickSort(q, j + 1, r);代码模版Java    public static void quickSort(int[] q, int l, int r){        if(l >= r) return;        int x = q[l + r >> 1], i = l - 1, j = r + 1;        while(i < j){            while( q[++i] < x );            while( q[--j] > x) ;            if(i < j){                int t = q[i];                q[i] = q[j];                q[j] = t;            }        }        quickSort(q, l, j);        quickSort(q, j + 1, r);    }C++void quick_sort(vector<int>&a,int l,int r){    if(l>=r)return;    int x=a[l+r>>1];    int i=l-1,j=r+1;    while(i<j){        while(a[++i]<x){        }        while(a[--j]>x){        }        if(i<j){            swap(a[i],a[j]);        }    }    quick_sort(a,l,j);    quick_sort(a,j+1,r);}Pythondef quick_sort(l,r,data):    if l >= r:        return    i = l - 1    j = r + 1    pivot = data[(i+j) // 2]    while i < j:        while 1:            i += 1            if data[i] >= pivot:                break        while 1:            j -= 1            if data[j] <= pivot:                break        if i < j:            data[i],data[j] = data[j],data[i]    quick_sort(l,j,data)    quick_sort(j+1,r,data)代码细节说明：代码中while循环中嵌套的两个while循环，之所以是指针先移动，再判断，是考虑一种特殊的情况，就是边界点恰好不满足上述情况，比如我们刚刚举的例子中指针第一次指向的元素6，就恰好不满足基准元素7的情况，因此在定义变量时，也是刻意让,这里while循环先移动还有一个好处就是可以避免死循环的情况，如果大家还是没太明白，建议直接背过代码，面试的时候面试官也不会care你的代码细节，你只要代码可以运行，而且能把思路讲的很清楚就基本ok。算法分析1.时间复杂度2.空间复杂度空间复杂度为O(1),不考虑递归使用的栈空间的话，是没有用到额外开辟的空间的。3.算法稳定性算法稳定性指的是，排序前后，相等元素的位置顺序不会被打乱，因此快速排序是不稳定的排序算法，我们没办法去保证相等元素顺序按照原有的顺序存放，因此是不稳定的排序算法。以上内容均来自于：面试刷题练习建议