java - 修改后的选择排序，选择最大的数字

Question

我正在尝试编写一个修改后的选择排序，它选择最大的数字并将其放置在列表的末尾。我遇到了问题。该代码对列表进行了某种排序，但并不完美。这是我运行代码后的结果: 选择排序前:[2,8,7,1,3,5,9,4,6] 选择排序后:[1, 2, 8, 7, 3, 4, 5, 9, 6]

这是我的代码:

public static int[] sort(int[] list) {
int i, j, maxNum, maxInde, temp = 0;
    for (i = list.length-1; i >= 0; i--) {
        maxNum = list[i];
        maxInde = i;
        for (j = i; j < list.length; j++) {
            if (list[j] < maxNum) {
                maxNum = list[j];
                maxInde = j;
            }
        }
        if (maxNum < list[i]) {
            temp = list[i];
            list[i] = list[maxInde];
            list[maxInde] = temp;
        }
    }
    return list;
}  

不知道问题出在哪里。

Answer 1

该算法在概念上存在缺陷，因为您从 n-1 扫描数组到 0，并在每次迭代时从子数组 a[n] 中选择最大元素-1,...,i]。该子数组应该始终被排序(并且应该由数组的 n-i 个最大元素组成)——这类似于经典选择排序的循环不变式——并且最大元素为插入当前位置的值应该来自另一个子数组，即 a[i,...,0]。

此外，正如评论中提到的，不需要返回数组，因为算法可以修改它。