Как изменить SelectionSort для отображения в порядке убывания? - PullRequest
Новая
       11

Как изменить SelectionSort для отображения в порядке убывания?

0 голосов
/ 04 ноября 2018

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

public void selectionSort()
{
    int n = data.length;

    for(int index = 0; index < n-1; index++)
    {
        int min_idx = index;
        for(int j = index+1; j < n; j++)
            if(data[j] < data[min_idx])
                min_idx = j;

        int temp = data[min_idx];
        data[min_idx] = data[index];
        data[index] = temp;
    }
}

Ответы [ 3 ]

0 голосов
/ 04 ноября 2018

Вместо того, чтобы выбирать минимальный элемент в каждой итерации, вы должны выбрать максимальный. Все, что вам действительно нужно сделать, это изменить условие < на >, но я также изменил имена соответственно, чтобы облегчить понимание кода: 

public void selectionSort()
{
    int n = data.length;

    for(int index = 0; index < n-1; index++)
    {
        int max_idx = index; // max_idx instead of min_idx
        for(int j = index+1; j < n; j++)
            if(data[j] > data[min_idx]) // > instead of <
                max_idx = j;

        int temp = data[max_idx];
        data[max_idx] = data[index];
        data[index] = temp;
    }
}
0 голосов
/ 04 ноября 2018

Чтобы решить эту проблему, я бы рекомендовал вам сначала выполнить рефакторинг вашего кода. Переместите swap и findMin в отдельный метод: 

private static int getMin(int[] arr, int from, int to) {
    int min = from;

    for (int j = from; j < to; j++)
        min = arr[j] < arr[min] ? j : min;

    return min;
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Здесь вы, вероятно, можете видеть, что реализация сортировки ASC и DESC тривиальна: 

public static void selectionSortAsc(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++)
        swap(arr, getMin(arr, i + 1, arr.length), i);
}

public static void selectionSortDesc(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--)
        swap(arr, getMin(arr, 0, i + 1), i);
}
0 голосов
/ 04 ноября 2018

На данный момент я могу думать о двух методах. Я не пробовал их, но стоит попробовать.

  1. Умножьте все числа на -1 и примените исходную сортировку выбора для сортировки по возрастанию. После завершения сортировки умножьте все числа на -1, чтобы получить исходные числа, но теперь они отсортированы в порядке убывания.

  2. Попробуйте изменить условие сравнения if (data [j] в if (data [j]> = data [min_idx])

Дайте мне знать, если есть какие-то проблемы с этими методами.

...