Выбор Sort не возвращает отсортированный массив

Question

Я пытаюсь написать сортировку выбора, где я нахожу максимум в массиве (sub), ограниченном верхним значением int, и меняю текущее значение на max.

Я написал три отдельных метода - у меня есть метод для нахождения индекса максимального значения в массиве, метод для замены двух значений и метод сортировки для фактической сортировки. Я попытался отладить, но не очень хорошо в этом ...

public static void sort(Comparable[] array)
   {
      int maxindex = 0;
      for(int k=0; k<array.length; k++)
      {
         maxindex = findMax(array, array.length-k);
         if(maxindex < k)
            swap(array, k, maxindex); 
      }   
   }

public static int findMax(Comparable[] array, int upper)
   {  //"upper" controls where the inner loop of the selection sort ends
      Comparable max = array[0];
      int maxindex = 0;
      for(int i = 1; i<upper; i++)
      {
         if(max.compareTo(array[i])<0)
         {
            max = array[i];
            maxindex = i;
         }
      }
      return maxindex;
   }

public static void swap(Object[] array, int a, int b)
   {
      Object save = array[b];
      array[b] = array[a];
      array[a] = save; 
   }

Я генерирую случайный массив и вызываю сортировку и распечатываю "отсортированный" массив, за исключением того, что печатный массив не сортируетсявообще ...

Answer 1

Так как сравнимый является необработанным типом. Ссылки на универсальный тип Comparable должны быть параметризованы. Не рекомендуется использовать необработанный тип данных, кроме случаев, когда это необходимо.

В приведенной ниже программе сделано несколько изменений из вашего кода. Вы можете сравнить, и он работает на сложности O (n ^ 2).

Основная проблема в вашем коде заключается в функции findMax () , функция делается статической путем жесткого кодирования значения.

import java.util.Arrays;

public class XYZ {
    public static void main(String args[]) {
        sort(new Integer[] { 1, 5, 2, 11, 4 });
    }

    public static void sort(Comparable[] array) {
        int maxindex = 0;
        for (int k = 0; k < array.length; k++) { 
            maxindex = findMax(array, k);
            if (maxindex > k)
                swap(array, k, maxindex);
            //  System.out.println(Arrays.toString(array));
        }
    }

    public static int findMax(Comparable[] array, int startIndex) {
        Comparable max = array[startIndex];
        int maxindex = 0;
        for (int i = startIndex; i < array.length; i++) {
            if (max.compareTo(array[i]) < 0) {
                max = array[i];
                maxindex = i;
            }
        }
        return maxindex;
    }

    public static void swap(Object[] array, int a, int b) {
        Object save = array[b];
        array[b] = array[a];
        array[a] = save;
    }
}

Answer 2

Я взял ваш код и внес некоторые изменения в sort, а также в функцию findMax. Теперь мы получаем правильный вывод.

1. sort функция: я не уверен, почему у вас есть условие перед свопом, это предотвратит обмен некоторых из findMax. Кроме того, я предполагаю, что вы делаете array.length - k, потому что вы, возможно, захотите сохранить максимум в последнем индексе и выполнить цикл, чтобы найти следующий максимум и так далее. Для этого ваша логика кажется неправильной.

2. findMax функция: индекс должен начинаться с 0 и идти до upper.

Подробности см. В приведенном ниже коде:

public static void sort(int[] array) {
    int maxindex = 0;
    for(int k=array.length - 1; k >= 0; k--) {
        maxindex = findMax(array, k);
        swap(array, k, maxindex);
    }
}

public static int findMax(int[] array, int upper) {  
    //"upper" controls where the inner loop of the selection sort ends
    int max = array[0];
    int maxindex = 0;
    for(int i = 0; i <= upper; i++) {
        if(max < array[i]) {
            max = array[i];
            maxindex = i;
        }
    }
    return maxindex;
}

Ввод: [4, 2, 3, 8, 7, 1, 9, 10, 15, 12, 11, 13]

Выход: [1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 15]