3回答

liuyubobobo

2020-11-13

已采纳

你是指这一小节的代码吗？

是的呀，这一小节的代码就是 arr[i, n)有序，arr[0, i)无序 呀。所以是换个方式实现选择排序呀。再仔细看一看上一小节的作业？

​

继续加油！：）

0

hiuyubobobo

回复

慕运维9331189

h 哦哦，我明白你的意思了。嗯，你是正确的。在每轮循环开始，是 arr(i, n) 有序，arr[0, i]。在循环后，维护了 i，使得 arr[i, n) 有序：）大赞！继续加油！：）

h020-11-16

共2条回复

假蛙工程师

2022-04-20

循环不变量不同，逻辑代码也不同

public static <E extends Comparable<E>> void sort(E[] arr) {

    // arr[0,i)已排序，arr[i, n)未排序
    for (int i = 0; i < arr.length; i ++) {
        int minIndex = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[j].compareTo(arr[minIndex]) < 0) {
                minIndex = j;
            }
        }
        swap(arr, minIndex, i);
    }
}

private static <E> void swap(E[] arr, int i, int j) {

    E temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static <E extends Comparable<E>> void sort2(E[] arr) {

    // arr[0,i) 无序的，arr[i,n)有序的
    for (int i = arr.length; i > 0; i --) {
        int maxIndex = i - 1;
        for (int j = i - 1; j >= 0; j --) {
            if (arr[j].compareTo(arr[maxIndex]) > 0) {
                maxIndex = j;
            }
        }
        swap(arr, i - 1, maxIndex);
    }
}

public static <E extends Comparable<E>> void sort3(E[] arr) {

    // arr[0,i]是无序的，arr(i,n)是有序的
    for (int i = arr.length - 1; i >= 0; i --) {
        int maxIndex = i;
        for (int j = i; j >= 0; j --) {
            if (arr[j].compareTo(arr[maxIndex]) > 0) {
                maxIndex = j;
            }
        }
        swap(arr, i , maxIndex);
    }
}

0

假蛙工程师

2021-10-16

老师的实现代码：
// 换个方法实现选择排序法，我们叫 sort2
public static <E extends Comparable> void sort2(E[] arr){

    for(int i = arr.length - 1; i >= 0; i --){

        // 选择 arr[0...i] 中的最大值
        int maxIndex = i;
        for(int j = i; j >= 0; j --){
            if(arr[j].compareTo(arr[maxIndex]) > 0)
                maxIndex = j;
        }

        swap(arr, i, maxIndex);
    }
}

我和题主的想法一样，循环变量应该是arr[0, i]未排序，arr(i, n)已排序。

d

在第一次进入训循环时， i = arr.length - 1 即 i = n - 1; 显然应该是arr(n - 1, n) 已排序，这是个空集合。

如果是arr[n-1, n)有序，就是说，还没开始排序，就存在部分元素是有序的，语义不通啊。

0