Java:选择排序我的实现与另一个

Question

下面是我对选择排序的实现:

package algorithm.selectionsort;

public class SelectionSort {

    public static void main(String[] args) {
        int[] myArray = selectionSort(new int[] { 9, 9, 9, 8, 7, 73, 32, 109, 1100, 432, 321, 0 });

        for (int element : myArray) {
            System.out.print("" + element + " ");
        }

    }

    public static int[] selectionSort(int[] a) {
        int min;
        for (int i = 0; i < a.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                    int temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;

                }
            }
        }
        return a;

    }

}

我注意到我的讲师对它的编码略有不同:

public static int[] selectionSort(int[] a) {
    int min;
    for (int i = 0; i < a.length - 1; i++) {
        min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;


            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
    return a;

}

两种实现都有效。我很好奇这里的区别是什么。是效率吗？

Answer 1

您和您的讲师的不同之处在于，他遍历数组并针对每个元素搜索最小值，然后与墙索引之后的元素执行交换。

对于你的，你遍历数组和每个元素，同时搜索最小值，如果当前值 < 则当前暂定最小值，与墙索引后的元素执行交换。

因此，您可以在最坏情况下交换 n*n 次，而不是交换 n 次:

你只交换一次通行证(最坏的情况):

100, 90, 88, 70, 55, 43, 32, 28, 19, 10
90, 100, 88, 70, 55, 43, 32, 28, 19, 10
88, 100, 90, 70, 55, 43, 32, 28, 19, 10
70, 100, 90, 88, 55, 43, 32, 28, 19, 10
55, 100, 90, 88, 70, 43, 32, 28, 19, 10
43, 100, 90, 88, 70, 55, 32, 28, 19, 10
32, 100, 90, 88, 70, 55, 43, 28, 19, 10
28, 100, 90, 88, 70, 55, 43, 32, 19, 10
19, 100, 90, 88, 70, 55, 43, 32, 28, 10
10, 100, 90, 88, 70, 55, 43, 32, 28, 19

您的讲师仅交换一次通行证(最坏情况):

100, 90, 88, 70, 55, 43, 32, 28, 19, 10
10, 90, 88, 70, 55, 43, 32, 28, 19, 100

本质上，您在搜索最小值的过程中交换值。您交换的“min”可能不是数组中的最低值。