😃快速排序的思想

快速排序的思想就是取数组中的某一个值，暂且叫做mid（但不一定是中间值），取两个指针，一个指针指向数组的首元素(left)，暂且叫做i，一个指针指向数组的尾元素(right)，暂且叫做j。

在i < j的条件下，执行以下操作：

i从左往右走，寻找>=mid的值
right从右往左走，寻找<=mid的值
两者都找到后，在i< j的情况下交换两者的值
继续上述操作

当循环条件不满足时，也就是 i >= j 时，数组会被分成两个区间，切记不是平分数组的两区间。可能会有一下几种情况：

可能是二等分,即[left, (left + right) / 2] 和 [(left + right) / 2 + 1, right]
也能是[left, left] 和 [left + 1, right]
或者[left, right - 1] 和 [right, right]

情况还有很多种，但是不管基于哪种情况都会满足左区间的值全部<=mid，右区间的值全部满足>=mid。

然后分别取左区间和右区间为一个新的数组，重复上述操作。当区间被划分到不存在时直接返回。

😕 快速排序演示图

快速排序动态演示图

😴 代码模板

void quick_sort(int a[], int left, int right) 
{
    if (left >= right) 
        return;
        
    int i = left - 1;    
    int j = right + 1;
    int mid = a[(left + right + 1) / 2];
    while (i < j) 
    {
        do i++; while (a[i] < mid);
        do j--; while (a[j] > mid);
        if (i < j) swap(a[i], a[j]);
    }
    
    quick_sort(a, left, i - 1);
    quick_sort(a, i, right);
}

?? `i` 和 `j` 的取值和循环处理 ??

🗽 `i` 和 `j` 的取值 🗽

由于在进行交换完之后，i和j都需要往中间走，所以不如在寻找交换值的时候先让这两个指针往中间靠一下，再进行判断，这样可以节省这一操作，简化代码。

但这样做的话，如果i 和 j的初始值为left 和 right 的话，就会跳过最左值和最右值的比较，所以需要让i比left小1，j比right大1。

当然，也可以根据个人个人习惯，在交换完之后先玩中间走，代码如下：

void quick_sort(int a[], int left, int right) 
{
    if (left >= right) 
        return;
        
    int i = left;    
    int j = right;
    int mid = a[(left + right + 1) / 2];
    while (i < j) 
    {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i < j) 
        {
        	swap(a[i], a[j]);
        	i++;
        	j--;
        }
    }
    
    quick_sort(a, left, i - 1);
    quick_sort(a, i, right);
}

🗽 循环条件判断 🗽

上述代码中寻找中间值的代码中while循环的条件能不能改成下面这样呢？

do i++; while (a[i] <= mid);
do j--; while (a[j] >= mid);
if (i < j) swap(a[i], a[j]);

答案是不可以的，如果数组中的值都是相等的话，在 i 有可能会变成 r + 1 ，然后执行 a[i] <= mid 语句，会导致数组访问越界。

💢 边界问题 💢

快速排序最让人头疼的莫非就是边界了，如果边界处理不当很有可能导致死循环和数组越界问题。

😵 什么是边界问题 😵

边界问题就是在划分新区间时使用左右指针中的哪一个来划分区间的问题，以及mid的取值问题。

😵 如何处理边界问题 😵

对于边界问题主要有一下节点需要注意：

使用左指针来划分区间时，新区间为：[left, i - 1], [i, right]
使用右指针来划分区间时，新区间为：[left, j], [j + 1, right]
使用左指针来划分区间时，mid的值不能取最左值
使用右指针来划分区间时，mid的值不能取最右值
使用中间值((left + right) / 2)作为mid时：如果使用左指针来划分区间，mid需要 +1。