Сортировка выбором в 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

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


java selection-sort
person Newbie    schedule 13.08.2014    source источник
comment
+1. Вы предоставили короткий код, ввод, ожидаемый вывод и фактический вывод.   -  person Cruncher    schedule 13.08.2014

Ответы (3)


arrow_upward
13
arrow_downward

Вы почти там.

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

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

Другой способ исправить код — оставить своп там, где он есть, но обновлять 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 */
}

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

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

person NPE    schedule 13.08.2014

arrow_upward
6
arrow_downward

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

         if (min !=i) {
                int temp = a[i];
                a[i] = a[min];
                a[min]= temp;
            }
person TheLostMind    schedule 13.08.2014
comment
О да, теперь я понял. Но что произойдет, если код подкачки окажется во внутреннем цикле? - person Newbie; 13.08.2014
comment
@Newbie - вы меняете местами каждый раз, когда ваше условие (min !=i) истинно. В конечном итоге вы замените значение, которое уже заменено, т. е. ваш массив будет фактически не по порядку (по отношению к ожидаемому результату каждой итерации) в итерация. - person TheLostMind; 13.08.2014

arrow_upward
6
arrow_downward

Почему вы не можете пойти с компаратором в сборе. Поскольку вы новичок в 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);
        }
    }
}
person Vinoth Babu    schedule 13.08.2014
comment
Это на самом деле не отвечает на вопрос, не так ли? - person NPE; 13.08.2014
comment
Это ответ на изменение подхода. :) - person Vinoth Babu; 13.08.2014
comment
Ваш класс является comparator, а не comparable, так что назовите его правильно. - person CodesInChaos; 13.08.2014