😃快速排序的思想

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

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

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

当循环条件不满足时，也就是 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。

😵 为什么要这样处理边界问题 😵

😫 区间划分问题 😫

这里以使用左指针来划分区间为例：

因为在循环结束时，数组被分为左右两个区间，i 的左边就是 <=mid的，a[i]的值一定是 >=mid的，所以[left, i - 1], [i, right]可以很好地将左右两个区间划分开来。

同理，使用右指针来划分区间时也是一样的道理。

😫 取最值问题 😫

这里以使用左指针来划分区间时，取最左值为例：

在循环结束时，因为 i 的最大值是 right 可能没有动，这时，左区间 [left, i - 1] 没有任何问题，但右区间 [i, right] 就会发生问题，因为 i 可能为 left ，会发生无限递归！！

举个栗子🤔：

当 mid 的值为 a[left]，数组中的元素 a[left, right] > mid 循环结束后，i == left, j == left ， 那么右区间就还会是原数组。

同理，在使用 j 来划分区间时 mid 取最右值也是一样的。

😫 mid 取中间值时是否需要 +1 问题 😫

这个问题就是取最值问题的一个派生问题，当数组中只有两个元素的话 mid 就会取到最左值，所以在使用左指针来划分区间时 mid 需要 +1，避免取到最左值的情况。

✨ 总结 ✨

快速排序的思想容易理解，但是边界问题却让人屡屡出错，所以我总结了一下几点经验：

1. 使用哪个指针，划分对应区间时需要往它起始的位置挪一下

使用左指针划分区间时，划分左区间 i 需要往左移一个位置，
使用右指针划分区间时，划分右区间 j 需要往右移一个位置。

2. 有加必有减

意思是如果mid +1 了，意味着使用的是做区间，那么对应的使用的左指针 i 就需要 -1。

有上面两句话基本上就可以搞定大部分的边界问题

完结散花🌈🌈🌈