C++快速排序代码中swap(words, start, current)未放入for循环的疑问

你提到的代码是快速排序的Lomuto分区实现版本，swap(words, start, current)放在for循环外是这个分区逻辑的标准设计，具体原因拆解如下：

第一步：先搞清楚基准元素的存放逻辑 #

进入当前递归的sort函数后，首先执行了swap(words, start, (start + end) / 2)，这步的作用是：

• 选出当前待排序子区间的中间元素作为分区基准
• 把基准元素临时交换到start位置存放，整个for循环遍历过程中，start位置的元素始终是固定的基准值，不会变动，所以所有元素都和*words[start]比对是完全正确的。

第二步：理解for循环的作用 #

循环中current变量的作用是记录当前已找到的「小于基准的元素」的最右下标，初始值为start：

• 遍历从start+1到end的所有元素，只要找到比基准小的元素，就先把current右移一位（给新的小元素腾位置），再把当前i位置的小元素和current位置的元素交换。
• 循环结束后，所有小于基准的元素，都已经被整理到了[start+1, current]这个区间里，current位置就是基准元素最终应该放的正确位置（左边全是小于它的元素，右边全是大于等于它的元素）。

第三步：为什么这个swap不能放进循环里 #

如果把swap(words, start, current)放到for循环内部，每次找到小元素就交换基准元素和current位置的元素，会直接破坏比对逻辑：

• 交换后start位置的元素就不再是原来的基准值了，后续遍历的元素和*words[start]比对时，参照值已经乱掉，完全无法完成分区功能。
• 我们只需要在所有元素比对完成后，把存放在start位置的基准，一次性交换到它最终的正确位置current即可，全程只需要执行一次这步交换。

小例子模拟验证 #

假设当前待排序子区间元素为["d", "a", "c", "b", "e"]，start=0，end=4：

1. 选中间位置下标2的元素"c"作为基准，交换到start位置，数组变为["c", "a", "d", "b", "e"]
2. 循环遍历：
   • i=1，"a"<"c"，current变为1，交换下标1和1，数组无变化
   • i=2，"d">"c"，不处理
   • i=3，"b"<"c"，current变为2，交换下标2和3，数组变为["c", "a", "b", "d", "e"]
   • i=4，"e">"c"，不处理
3. 循环结束，current=2，交换start=0和current=2，数组变为["b", "a", "c", "d", "e"]，基准"c"落到正确位置，分区完成。

内容的提问来源于stack exchange，提问作者konanrash