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" 可能不是数组中的最低值。

Answer 2

当然你导师的代码更高效也更优雅。什么是选择排序？

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

如果待排序列表的长度是n，那么只需要n次交换，但是在你的代码，它是 n*(n-1)*(n-2)....

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

Java: Selection Sort My implementation vs. another

java

selection-sort