java - 如何纠正我的选择和插入排序算法

Question

我编写的选择和插入排序算法给了我错误的未排序输出。这是我的选择排序代码:

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]+" ");
        }


    }

}

Output: 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] + " ");
        }

    }
}

Output: 2 4 5 4 3 5 3 6

Answer 1

在选择排序中，让我们重点关注这部分代码:

    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 处的元素交换。请注意，使用此处的代码，您不断地将当前索引与最小值的索引交换，这不是您想要进行的交换。作为提示，外循环的每次迭代最多进行一次交换，并且该交换位于位置 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;