大厂面试高频题：快速排序【算法讲解&多语言代码模版】

快速排序是一种常见的排序算法，也是面试中面试官很喜欢考察的一种算法，据不完全统计，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);
}

Python

def 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。