循环不变量定义

老师，我觉得第二种实现选择排序的方法中应该是：arr(i, n)有序，arr[0, i]无序。
我觉得您实现的代码是这个意思。
而不是上课讲的：arr[i, n)有序，arr[0, i)无序。
不知道我想的对不对。

慕运维9331189 2020-11-13

源自：排序基础 1-7 换个角度实现选择排序法，作业分析

收起

3回答

liuyubobobo 回答被采纳获得+3积分 2020-11-13 13:28:15

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

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

继续加油！：）

收起回答

慕运维9331189 提问者 #1

老师，你文字给出的代码：初始时 i = arr.length - 1。如果按照您定义的arr[i, n)有序，arr[0, i)无序，那么此时最后一个元素就是有序的。对于选择排序来说，这应该不对吧。所以，我觉得应该是arr(i, n)有序，arr[0, i]无序。也就是开和闭上有些分歧，您再看看？

2020-11-15 10:26:49
liuyubobobo 回复提问者慕运维9331189 #2

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

2020-11-16 02:02:12

假蛙工程师 2022-04-20 17:58:22

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

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);
    }
}

收起回答

假蛙工程师 2021-10-16 10:49:10

老师的实现代码：
// 换个方法实现选择排序法，我们叫 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);
    }
}