Выбор Сортировка на Java дает неверные результаты

Я новичок в 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

Я делаю небольшую ошибку, которую я не могу понять. Может кто-нибудь, пожалуйста, помогите мне исправить это?

Ответ 1

Ты почти там.

Часть, которая меняет элементы, должна находиться вне внутреннего цикла.

Другими словами, вам нужно сначала найти наименьший элемент в остальной части массива, а затем поменять его на текущую позицию. Прямо сейчас вы меняете местами, как только найдете меньшее число, и в процессе не отслеживаете новую позицию этого меньшего числа.

Еще один способ исправить код - сохранить подкачку, где он есть, но обновить min после каждого свопа:

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

Это тоже будет работать, но довольно неэффективно.

P.S. Проверка if (min != i) не нужна, так как замена элемента с самим собой является безобидным no-op.

Ответ 2

Вы меняете элементы для каждой итерации внутреннего цикла. Поместите нижний блок за пределы внутреннего цикла. Вы должны поменять местами только для каждой итерации внешнего цикла.

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

Ответ 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);
        }
    }
}