选择排序算法优化疑问：能否删除中间变量minIndex？

嘿，这个问题问得挺实在的！咱们直接说结论：确实可以删掉minIndex，直接在遍历j的过程中交换i和j位置的元素，但这么做会牺牲选择排序原本的效率优势，咱们来仔细掰扯掰扯。

先看修改后的代码实现 #

你可以把代码改成这样，完全能完成排序：

public static void sort(int[] arr){
    int n = arr.length;
    for( int i = 0 ; i < n ; i ++ ){
        for( int j = i + 1 ; j < n ; j ++ ){
            // 直接拿当前j位置元素和i位置元素比较，小就交换
            if( arr[j] < arr[i] ){
                swap( arr , i , j);
            }
        }
    }
}
private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

核心差异：交换次数的天差地别 #

选择排序的核心设计思路就是每轮只做一次交换——先把未排序区间里的最小值找出来，最后再和当前i位置的元素交换。而修改后的逻辑是每遇到一个更小的元素就立刻交换，这会导致交换次数暴增：

• 原算法：不管未排序区间有多少个比arr[i]小的元素，每轮i循环最多只交换1次，整个排序过程最多做n-1次交换。
• 修改后算法：每遇到一个比当前arr[i]小的元素就交换，极端情况下（比如数组完全倒序），每轮i循环会做n-i-1次交换，总交换次数会达到O(n²)级别，和冒泡排序的交换次数差不多。

举个直观的例子，比如数组是[5,4,3,2,1]：

• 原算法第一轮i=0：找到最小值索引4，最后只交换1次，数组变成[1,4,3,2,5]。
• 修改后算法第一轮i=0：j=1时交换→[4,5,3,2,1]；j=2时交换→[3,5,4,2,1]；j=3时交换→[2,5,4,3,1]；j=4时交换→[1,5,4,3,2]，这一轮就做了4次交换。

总结 #

修改后的代码功能上是可行的，但完全丢掉了选择排序“交换次数少”的核心优势，效率大打折扣。如果追求排序的正确性，这么写没问题，但如果要遵循选择排序的设计初衷，保留minIndex才是更合理的做法。

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