Почему этот алгоритм не сортирует последний индекс правильно?

Question

Я должен написать версию алгоритма сортировки выбора, который перемещает наименьшее число в начало массива, одновременно перемещая наибольшее число в конец массива.Я понимаю, что это в основном работает с обоих концов, так что есть два отсортированных под-массива, однако мой код, кажется, неправильно помещает последнее число в массиве.Мой код:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;
        for (int j=i+1;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        int temp1=a[min];
        int temp2=a[max];
        a[min]=a[i];
        a[max]=a[(a.length-1)-i];
        a[i]=temp1;
        a[(a.length-1)-i]=temp2;
    }
}

Если задан вход [5,4,3,2,1], он выводит [1,2,5,3,4] вместо [1,2,3,4,5].Чего мне не хватает?

Answer 1

Проблема во внутреннем цикле.

Это начинается с i + 1.Таким образом, код для сравнения max фактически сравнивает [1] с [4].

, вы можете изменить его на for (int j=i;j<a.length-i;j++)

Также, как вы можете прочитать в комментарии, может бытьслучай, когда с вышеупомянутым изменением код все еще не будет работать.Это произойдет, потому что i == max и, следовательно, существующий подход подкачки не будет работать.Например: предположим, что array = [6,4,5], внутренний цикл max = 0, min = 1. Существующий своп сделает это [4,6,6].Следовательно, своп должен обрабатываться по-разному.

      if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }  

Полный код приведен ниже:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;

        for (int j=i;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }       
    }
}

public static void swap(int[] a,int i,int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Answer 2

В каждой итерации внешнего цикла вы начинаете с первого индекса (i) в качестве начального минимального индекса и последнего индекса (a.length-1-i) в качестве начального максимального индекса.Затем вы сравниваете оба этих индекса со всеми индексами в диапазоне от i + 1 до a.length-i-1.Но если первый индекс (i) фактически содержит значение max, вы никогда не сравните его с [max], поэтому [max] никогда не будет содержать правильное значение в конце внутреннего цикла.

Вотпредлагаемое исправление:

public static void dualSelectionSort(int[]a) {
    for(int i = 0; i < a.length - i - 1; i++) {
        if (a[i] > a[(a.length - 1) - i]) {
            int temp = a[i];
            a[i] = a[(a.length - 1) - i];
            a[(a.length - 1) - i] = temp;
        }
        int min = i;
        int max = (a.length - 1) - i;
        for (int j = i + 1; j < (a.length -1 ) - i; j++) {
            if(a[j] < a[min]) {
                min = j;
            }
            if(a[j] > a[max]) {
                max = j;
            }
        }
        int temp1 = a[min];
        int temp2 = a[max];
        a[min] = a[i];
        a[max] = a[(a.length - 1) - i];
        a[i] = temp1;
        a[(a.length - 1) - i] = temp2;
    }
}

Три вещи, которые я изменил:

1. Внешний цикл может закончиться гораздо раньше, чем вы его завершите - один раз i >= a.length-i-1 - так как вНа каждой итерации вы находите минимальное и максимальное значение, поэтому вы уменьшаете оставшийся несортированный массив на 2.

2. При инициализации индексов min и max убедитесь, что индекс minна самом деле содержит значение меньше индекса max.Если a[i] > a[(a.length-1)-i], поменяйте их местами перед установкой min на i и max на (a.length-1)-i.

3. Внутренний цикл должен повторяться j с i+1 на(a.length-1)-i-1.