Java - Selection排序算法

Question

我有一些关于选择排序的问题，我有点困惑。

 int [] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;//Selection sort algorithm says that find the minimum in the
                // array, but first element is not minimum.What's point here?
        for(int j = i + 1;j<arr.length;j++)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            System.out.println(arr[i]);//I print the in ascending order 
        }
    }

输出为：

4
3
2
1
4
3
2
4
3
4

出什么事了？

Answer 1

选择排序是在循环的每一步中找到最小值。你没有找到最小值(可能是通过if语句)，只是在你的内部循环中简单地交换了这个值。所以你实际上没有做排序。

根据您的实现进行更正：

final int[] arr = { 5, 4, 3, 2, 1 }; // This is my array
    int min;
    for (int i = 0; i < arr.length; i++) {
        // Assume first element is min
        min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;

            }
        }
        if (min != i) {
            final int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        System.out.println(arr[i]);// I print the in ascending order
    }

这应该会给出输出：

1
2
3
4
5

Answer 2

正确：

public class Test {

public static void main(String args[]){
    int[] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;
        for(int j = i + 1;j<arr.length;j++)
        {
            if(arr[j] < arr[min]) { min = j;}
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
        System.out.println(arr[i]);//I print the in ascending order 
    }
}

}

关于min部分:它只是指当前min的索引。您继续向下移动数组，直到遇到新的min，并将min设置为该索引。因此，在看到4之前，5是min =0的最小值，所以现在min=1，但是当min=1时，您将3与存储在4时的任何值进行比较，然后意识到您应该设置min=2……等等等等。

Answer 3

您的问题似乎在您的评论中

min = i;//Selection sort algorithm says that find the minimum in the
        // array, but first element is not minimum.What's point here?

重点是你可以假设你正在检查的第一个是最低的，这样你就有了一个开始的地方。毕竟，它可能不是所有的最小值，但在你在这次迭代中检查的一个迭代中，它是到目前为止最低的！