Selection Sort in Java produces incorrect results

问题:

I am new to Java and I am trying to write a selection sort program. Below is my code :

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]);
        }
    }
}

My input array is 6,4,9,3,1,7. The sorted output should be 1,3,4,6,7,9 But the output I am getting is:

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

I am doing some small mistake which I am unable to figure out. Can anyone please help me fix it?

回答1:

You are almost there.

The part that swaps elements should be outside the inner loop.

In other words, you need to first find the smallest element in the remainder of the array, and then swap it into the current position. Right now you're swapping as soon as you have found a smaller number, and in the process failing to keep track of the new position of this smaller number.

Another way to fix the code is to keep the swap where it is, but update min after each swap:

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 */
}

This too will work, but is rather inefficient.

P.S. The if (min != i) check is unnecessary since swapping an element with itself is a harmless no-op.

回答2:

You are swapping the elements for each iteration of inner loop Put the below block outside the inner loop. You should swap only for each iteration of outer loop.

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

回答3:

Why cant you go with comparator in collection. As you are new to java, you can learn the feature provided by java too. Check the below example for that.

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);
        }
    }
}