这是我参与8月更文挑战的第5天，活动详情查看：8月更文挑战

想要坚持写点什么，那干脆写一个系列吧。想想有什么可以写的呢？程序=算法+数据结构，可见算法的重要性。这个系列老诗力求用最简单的语言把算法讲得明明白白，由浅到深，有兴趣的话，可以关注一下专栏。

在面试中，经常会考到快速排序算法，考官可能不会让你手写快速排序，但是其中的原理你必须得讲明白才行。重要的东西需要记住，并且复述出来。

快速排序算法描述

1首先设定一个分界值，通过这个值将数组分成左右两部分。

2将大于或等于分界值的数放在分界值的右边，反之放在分界值的左边。

3然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序图示

假设一开始序列x数组是：5，3，7，6，4，1，0，2，9，10，8。

首先，ref=5，i=1，j=10，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。

此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。

此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

快速排序实现

#include <iostream>
 
using namespace std;
 
void Qsort(int arr[], int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true)
    {
        /*从左向右找比key大的值*/
        while (arr[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*从右向左找比key小的值*/
        while (arr[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交换i,j对应的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中枢值与j对应值交换*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    Qsort(arr, low, j - 1);
    Qsort(arr, j + 1, high);
}
 
int main()
{
    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
 
    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
 
    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
        {
        cout << a[i] << " ";
    }
     
    return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/
复制代码

快排是我见过最常见的考官面试排序算法，所以小伙伴有面试需要的话，尽量还是研究清楚吧。

想要学习更多算法问题，或者要更多项目源码，请移步到公众号：诗一样的代码。

既然进来了。小伙伴点个赞再走呗。