Как я могу исправить мои алгоритмы сортировки выбором и вставкой

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

public class SelectionSort {

    public static void main(String[] args) {

        int[] arr = {23,43,45,3,54,55,23,12,22};

        int min;
        int temp = 0;

        for(int i = 0; i < arr.length-1; i++)
        {
            min = i;
            for(int j = i+1; j<arr.length; j++)
            {
                if(arr[j] < arr[min])
                {
                    min = j;

                }
                temp = arr[j];
                arr[j] = arr[min];
                arr[min] = temp;
            }

        }

        for(int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i]+" ");
        }


    }

}

Выход: 45 55 54 43 23 23 22 12 3

Это не отсортировано, и я хочу, чтобы оно сортировалось в порядке возрастания.

Вот моя сортировка вставками:

public class Insertion {

    public static void main(String[] args) {

        int[] arr = {2,4,6,5,4,3,5,3};

        for(int i = 1; i < arr.length; i++)
        {
            int temp = arr[i];

            int j = i;

            while( j > 0 && arr[j-1] > arr[j])
            {
                arr[j] = arr[j-1];
                j = j-1;
            }
            arr[j] = temp;
        }

        for(int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");
        }

    }
}

Выход: 2 4 5 4 3 5 3 6


java sorting selection-sort insertion-sort
person ous    schedule 22.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В сортировке выбором давайте сосредоточимся на этой части кода:

    for(int i = 0; i < arr.length-1; i++)
    {
        min = i;
        for(int j = i+1; j<arr.length; j++)
        {
            if(arr[j] < arr[min])
            {
                min = j;

            }
            temp = arr[j];   // <---
            arr[j] = arr[min];
            arr[min] = temp;
        }
    }

Основная идея сортировки выбором состоит в том, чтобы найти наименьший элемент в диапазоне [i, n), а затем поменять его местами с элементом в позиции i. Обратите внимание, что в коде, который у вас есть, вы постоянно меняете текущий индекс на индекс min, а это не та замена, которую вы хотите сделать. В качестве подсказки сделайте не более одного обмена за итерацию внешнего цикла, и пусть этот обмен будет между позицией i и позицией min. Если вы поменяетесь местами раньше, вы получите неправильный ответ.

Для вашей сортировки вставками есть более тонкая ошибка. Вот где ошибка:

while( j > 0 && arr[j-1] > arr[j])
{
    arr[j] = arr[j-1];
    j = j-1;
}
arr[j] = temp;

Обратите внимание, что всякий раз, когда текущий элемент сравнивается меньше, чем предыдущий элемент, вы перезаписываете текущий элемент с элементом перед ним, а затем уменьшаете j. Однако вы не обновляете arr[j-1] текущим элементом, поэтому при следующем сравнении вы сравниваете элемент, который раньше находился в позиции j-1, с элементом, который находится в позиции j-2, а не сравниваете текущий элемент с элементом в позиция j-2. Чтобы исправить это, обновите сравнение, чтобы всегда сравнивать с temp, а не с arr[j]:

while( j > 0 && arr[j-1] > temp)
{
    arr[j] = arr[j-1];
    j = j-1;
}
arr[j] = temp;
person templatetypedef    schedule 27.08.2015