算法模式：循环排序
在上一篇文章 算法模式：快速选择 介绍了如何利用快排思想快速选出第 K 个 最 X 的元素。本篇文章，介绍一种只需 \$O(1)\$ 时间就可以完成排序的算法模式：循环排序。
循环排序
循环排序讲述的是一种很好玩的模式：可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上，但这复杂度就会是 \$O(n^2)\$。这样的话，可能就不是最优解了。因此循环排序的优势就体现出来了。
循环排序适用的场景：
包含连续数字的数组（如 1 到 n 或 0 到 n-1）
需要找出缺失/重复数字的问题
需要原地排序且时间复杂度要求高的情况
LeetCode 41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \$O(n)\$ 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
思路分析
这道题的思路很简单：如果数组元素在 0 到数组长度内，并且数组元素不在对应的下标（数组元素 - 1），则将数组中数组元素当前下标与对应的下标（数组元素 - 1）进行交换。超出范围的，或已经在对应下标上的，则直接跳过即可。处理完成后，再从前向后遍历数组，找出第一个缺失数字。如果没有缺失，则第一个数字就是数组长度 + 1。代码如下：
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-27 22:16:54
*/
public int firstMissingPositive(int[] nums) {
int length = nums.length;
for (int i = 0; i < length; ) {
int num = nums[i];
// 相比官方题解，这里利用判断，减少了一层循环，更容易理解
if (0 < num && num < length && num != nums[num - 1]) {
// 元素在数组长度范围内，并且不在数字对应的下标（num-1）的位置就交换
int temp = nums[num - 1];
nums[num - 1] = num;
// 要交换 i 与 num -1
nums[i] = temp;
} else {
// 只有在当前位置无法处理（超出数组访问）
// 或无需处理（数字与下标对应）时，才向前推进
i++;
}
}
// 从前向后遍历，第一个数字和下标不对应的数字就是答案
for (int i = 0; i < length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return length + 1;
}在解答 442. 数组中重复的数据 时发现，在本题中可以省略的一层循环，在 442. 数组中重复的数据 中却不能省略。这道题之所以可以省略，是因为这道题的题目有一个隐含条件：它不关注重复元素的个数，或者说它把所有元素都当做不可重复的元素了。但是， 442. 数组中重复的数据 中却存在多个重复元素，所以，不使用循环来把元素放到自己的位置上，会导致交换一次后，新元素还是不再自己本应所在的位置。 |
