пытаюсь реализовать сортировку выбором, но это не сработает

В настоящее время я работаю над проектом, в котором реализую различные типы методов сортировки для сортировки массива. Я получил эту реализацию из своего класса, но по какой-то причине она не работает. Я не уверен, где все идет не так, и любая помощь будет принята с благодарностью.

public static void selectionSort(int[] a) {
    int n = a.length;
    System.out.println(n);
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                int swap = a[i];
                a[i] = a[min];
                a[min] = swap;
            }
        }
    }
}

Алгоритм: Находит минимальное значение в списке. Заменяет его значением в первой позиции. Повторите описанные выше шаги для остальной части списка (начиная со второй позиции и продвигаясь каждый раз). Он делит список на две части. Подсписок элементов уже отсортирован. Подсписок элементов, оставшихся для сортировки.

вход

int[] a = new int[]{-2, 4, 8, 1, 9, -6};

ожидаемый результат

-6, -2, 1, 4, 8, 9

java arrays sorting selection-sort
person Paul Anthony Morillo    schedule 10.05.2019    source источник
comment
int min = i;, а затем a[i] = a[min]; - что он делает?   -  person PM 77-1    schedule 10.05.2019
comment
Опишите механизм сортировки. Вход, текущий выход и ожидаемый результат.   -  person Roshana Pitigala    schedule 10.05.2019
comment
Алгоритм: Находит минимальное значение в списке • Заменяет его значением в первой позиции • Повторяет описанные выше шаги для оставшейся части списка (начиная со второй позиции и продвигаясь каждый раз) • Он делит список на две части. • Подсписок уже отсортированных элементов. • Подсписок элементов, которые еще предстоит отсортировать.   -  person Paul Anthony Morillo    schedule 10.05.2019
comment
@RoshanaPitigala, я не уверен, что вы подразумеваете под механизмом сортировки, но текущий ввод представляет собой массив (-2,4,8,1,9,-6), а текущий вывод имеет тот же порядок ввода. ожидаемый результат равен (-6,-2,1,4,8,9)   -  person Paul Anthony Morillo    schedule 10.05.2019

Ответы (3)


arrow_upward
1
arrow_downward

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

public static void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
                int swap = a[i];
                a[i] = a[min];
                a[min] = swap;
            }
        }
    }
}
person Sumit Bhardwaj    schedule 10.05.2019

arrow_upward
1
arrow_downward

Проблема заключается в цикле for, переменных min и i.

int min = i; //min variable is useless, as min is always equals to i
for (int j = i + 1; j < n; j++) {
    if (a[j] < a[min]) {
        int swap = a[i];
        a[i] = a[min]; // remember min equals to i, so here you are assigning the same value
        a[min] = swap; // this should be a[j]
    }
}

Измените цикл for

for (int j = i + 1; j < n; j++) {
    if (a[j] < a[i]) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}
person Roshana Pitigala    schedule 10.05.2019

arrow_upward
1
arrow_downward

Вы можете просто использовать класс java.util.Arrays для этого

int[] a = new int[]{-2, 4, 8, 1, 9, -6};
Arrays.sort(a);

это сортирует массив a в порядке возрастания (ваш ожидаемый результат).

Java предварительно собрана с несколькими инструментами. Всегда ищите их, писать собственный алгоритм весело, но может быть ошибочно и кропотливо.

person Roshana Pitigala    schedule 10.05.2019