插入排序输出不符合预期

Question

我的插入排序输出不正确。当我尝试调用 insertionSort 方法时，返回的数组未排序

break语句的使用是否正确？

public int[] insertionSort(int [] arr){
    for(int i=1;i<arr.length;i++){
        for(int j=0;j<=i-1;){
            int temp;
            if(arr[i] < arr[j]){
                temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; 
                break;
            }
            else j++;
            }
        }
        return arr;
}

用 int [] array = {10,5,6,7,1,9,3,8} 调用了方法，但结果不正确：

Output After Sorting: 1, 3, 7, 8, 5, 10, 6, 9, // output is not sorted but it changed by somewhat

Answer 1

这是有效的代码：

public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                // Swap
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;

                j--;
            }
        }
        return arr;
    }

您的代码存在的一个问题是您会将 i-th 元素放在正确的位置，但可能会弄乱已经位于正确位置的元素的位置。

插入排序的思想是在正确的位置插入i-th个元素，也就是说你要把所有的元素都向右移动。但是，在您的情况下，您只需在找到正确的位置后交换 j-th 元素和 i-th。

例子： 1 3 5 8 10 这是数组的当前状态现在你尝试插入元素6，你发现正确的位置是3，所以你交换它们，结果是： 1 3 5 6 10 8 弄乱了数字 8.

的位置

插入排序输出不符合预期

Insertion Sort output is not as expected

java

arrays

sorting

break

insertion-sort