选择在Java中排序会产生不正确的结果

Question

我是Java的新手,我正在尝试编写一个选择排序程序.以下是我的代码:

public class SelectionSort {
    public static int a[] = {6, 4, 9, 3, 1, 7};

    public static void main(String[] args) {
        int min, i, j;
        for(i = 0; i < a.length - 1; i++) {
            min = i ;
            for(j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j; 
                }
                if (min != i) {
                    int temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;
                }
            }
        }
        for (i = 0; i < a.length; i++) {
            System.out.println("a : " + a[i]);
        }
    }
}

我的输入数组是6,4,9,3,1,7.排序的输出应该是1,3,4,6,7,9 但我得到的输出是:

a : 3
a : 4
a : 6
a : 7
a : 1
a : 9

我正在做一些我无法弄清楚的小错误.有人可以帮我解决一下吗？

Answer 1

你快到了.

交换元素的部分应该在内部循环之外.

换句话说,您需要首先在数组的其余部分中找到最小元素,然后将其交换到当前位置.现在,只要找到一个较小的数字,就会进行交换,并且在此过程中无法跟踪这个较小数字的新位置.

修复代码的另一种方法是保持交换位置,但min在每次交换后更新:

if (min !=i) {
    int temp = a[i];
    a[i] = a[min];
    a[min]= temp;
    min = i;       /* Update `min' to reflect the number's new position */
}

这也可行,但效率很低.

PS if (min != i)检查是不必要的,因为交换元素本身是一个无害的无操作.

Answer 2

您正在为内循环的每次迭代交换元素将下面的块放在内循环之外.您应该只交换外循环的每次迭代.

         if (min !=i) {
                int temp = a[i];
                a[i] = a[min];
                a[min]= temp;
            }

Answer 3

为什么你不能用比较器收集.由于您是java新手,您也可以学习java提供的功能.检查以下示例.

import java.util.Comparator;

public class MyIntComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return (o1>o2 ? -1 : (o1==o2 ? 0 : 1));
    }
}
--------------------------------------------------------
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Simple2 {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(5);
        list.add(4);
        list.add(3);
        list.add(7);
        list.add(2);
        list.add(1);
        Collections.sort(list, new MyIntComparable());
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }
}