选择最大数的改进选择排序

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，并且在每次迭代时 select 子数组 a[n-1,...,i] 中的最大元素。该子数组应始终排序（并且应由数组的 n-i 最大元素组成）---这类似于经典 selection 排序的循环不变式---和最大元素要插入当前位置的应该来自另一个子数组，即 a[i,...,0].

此外，如评论中所述，不需要return数组，因为算法可以修改它。

Answer 2

这里是固定版本：

int i, j, maxNum, maxInde, temp = 0;
for (i = list.length-1; i >= 0; i--) {
// you start iterating from the end of the list 
// which means that the elements between i and the end of the list are sorted
    maxNum = list[i];
    maxInde = i;
    for (j = 0; j < i; j++) { 
    // you have to iterate through the nonsorted elements
        if (list[j] > maxNum) {
            maxNum = list[j];
            maxInde = j;
        }
    }
    if (maxNum > list[i]) {
    // if you found an element that is bigger then the current element
    // then it should be set as the current element
        temp = list[i];
        list[i] = list[maxInde];
        list[maxInde] = temp;
    }
}

选择最大数的改进选择排序

Modified selection sort that selects the biggest number

java

arrays

sorting

sorted

selection