在选择排序中，如果我们有两个重复元素，算法的行为是什么？

Question

如果我们从下面的代码（最后一部分）中删除以if (indexMax != i)开头的部分，算法就会崩溃，为什么？

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int indexMax = i;

        for (int j = i + 1; j < array.length; j++) {
            if (array[indexMax] < array[j]) {
                indexMax = j;
            }
        }

        if (indexMax != i) {
            int temp = array[i];
            array[i] = array[indexMax];
            array[indexMax] = temp;
        }
    }
}

Answer 1

根据您在我的评论中发布的代码：

    int indexMax = i;  // initial value of indexMax

    for (int j = i + 1; j < array.length; j++) {
        // please note that j starts with (i+1)
        if (array[indexMax] < array[j]) {
            indexMax = j;  // index of Max candidate  
        }
    }

    if (indexMax != i) {   // means that the above loop reassigned indexMax
        int temp = array[i];  // so we are swapping
        array[i] = array[indexMax];
        array[indexMax] = temp;
    }

所以 if (indexMax != i) 的意思是“我们找到更好的 Max 了吗？”

Answer 2

您的代码将执行以下操作：

arr[] = 1, 5, 2, 4, 3

// find the max from arr[0..4]
// substitute it with the index 0, if it is not of that index already
arr[] = 5, 1, 2, 4, 3

// find the max from arr[1..4]
// substitute it with the index 1, if it is not of that index already
arr[] = 5, 4, 2, 1, 3 

// find the max from arr[2..4]
// substitute it with the index 2, if it is not of that index already 
arr[] = 5, 4, 3, 1, 2

// find the max from arr[3..4]
// substitute it with the index 3, if it is not of that index already 
arr[] = 5, 4, 3, 2, 1

用索引i代替它，如果它已经不是那个索引就是那个if语句

要获得更长的重复数组，请查看我为您创建的 Kotlin Playground Code。你可以随意更改数组，并且可以跟踪值的切换。

Answer 3

在图片中您可以看到重复项目如何移动它们的相对 position.This 引入不稳定性。

三个重复项：

对于两个重复的项目：

在选择排序中，如果我们有两个重复元素，算法的行为是什么？

In selection sort, if we have two duplicate elements, what is the behavior of the algorithm?

java

algorithm

sorting

selection-sort