力扣第75题新思路：如何用选择排序实现原地操作？

给定一个包含红色、白色和蓝色元素的数组，分别用数字 0、1、2 表示，要求在不使用库排序函数的情况下，仅通过一次遍历（但实际上允许使用经典排序方法）对数组进行原地排序。题目要求将所有 0 排在前面，1 排在中间，2 排在最后，且需要保持元素间的相对顺序。本题的核心是实现一个高效的原地排序算法，但所提供的代码通过经典的选择排序思想完成目标。

选择排序的核心思路是：每次从未排序区间中找到最小值，将其与未排序区间的第一个元素交换，逐步扩展有序区间的范围。具体过程如下：

1‌.外层循环控制有序区间‌：从第一个元素开始，依次向后遍历，每次确定一个位置的最终值。

‌2.内层循环寻找最小值‌：对于当前未排序的位置 i，通过内层循环遍历其后的所有元素，寻找最小值的索引 minIndex。

3‌.元素交换‌：将找到的最小值与当前外层循环的位置 i 的元素交换，确保每次外层循环结束后，区间 [0, i] 是有序的。

4‌.逐步扩展有序范围‌：重复上述过程，直到整个数组有序。

5.时间复杂度为 O(n²)，空间复杂度为 O(1)。

代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();      // 获取数组长度
        int minIndex = 0;         // 记录最小值的位置
        
        // 外层循环：逐步确定每个位置的元素
        for (int i = 0; i < n; i++) {
            minIndex = i;         // 初始最小值位置为当前未排序区间的首位
            
            // 内层循环：在未排序区间中寻找最小值的位置
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j; // 更新最小值的位置
                }
            }
            
            // 将最小值与当前位置交换，确保当前位置的值是最终结果
            int tmp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = tmp;
        }
    }
};