java为什么我的选择排序代码不起作用？

Question

我有这个选择排序功能：

public static void selectionSort(int[] n)
{
    for(int start = 0; start < n.length; start++)
    {
        int smallest = start;

        for(int i = start+1; i<n.length; i++)
            {if(n[i]<n[start])
                smallest = i;}

        int tmp = n[start];
        n[start] = n[smallest];
        n[smallest] = tmp;
    }
}

我这样称呼它

Random ran = new Random();
    int n = 10;
    int[] a = new int[n];

    for(int i = 0; i<n; i++)
        a[i] = ran.nextInt(1000);

然而，它会导致这样的结果

640 900 610 168 650 610 527 356 802 486

486 640 356 168 610 527 610 650 802 900

上面的一个没有排序，下面的一个应该排序。然而，这是不正确的

Answer 1

第二个循环是无用的，因为您毕竟只是在比较第一个和最后一个项目，而smallest只从这个比较中获取它的值。 根据你的代码，我猜你想做一个Bubble Sort，但是比较和索引管理是错误的，这里有一个可行的解决方案：

public static void main(String[] args) {
    Random ran = new Random();
    int n = 10;
    int[] array = new int[n];

    for (int i = 0; i < n; i++) {
        array[i] = ran.nextInt(1000);
    }

    printArray(array);
    selectionSort(array);
    printArray(array);
}

private static void printArray(int[] array) {
    System.out.print("Array: ");
    for (int i : array) {
        System.out.print(i + " ");
    }
    System.out.println();
}

private static void selectionSort(int[] array) {
    for (int j = 0; j < array.length; j++) {
        // Subtract 1 so you don't get a NullPointerException
        // Subtract j so you don't compare the numbers already ordered
        for (int i = 0; i < array.length - 1 - j; i++) {
            if (array[i] > array[i + 1]) {
                int tmp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = tmp;
            }
        }
    }

}

该算法取自上面链接的Spanish version（我来自阿根廷），该链接的英文版本也带有其他符号

希望这有帮助。致意

Answer 2

每次迭代都会比较初始start索引，即使找到了较小的数字，也会将其与不应该发生的原始start进行比较。一旦你找到一个较小的数字，你就需要使用这个索引进行比较

将其与每次迭代的最小值进行比较，将(n[i]<n[start])更改为(n[i]<n[smallest])，这将解决您的问题

希望这有帮助

Answer 3

试着使用这个版本的代码，它的功能是：

    public static void main(String[] args) {
    Random ran = new Random();
    int n = 10;
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
        a[i] = ran.nextInt(1000);
    selectionSort(a);
    for (int i : a) {
        System.out.print(i+" ");
    }
}

public static void selectionSort(int[] n)
{
    for(int start = 0; start < n.length-1; start++)
    {
        int smallest = start;

        for(int i = start+1; i<n.length; i++)
        {if(n[i]<n[smallest])
            smallest = i;}

        int tmp = n[start];
        n[start] = n[smallest];
        n[smallest] = tmp;
    }
}