Java 插入排序错误

Question

我试图通过书中的伪代码在 java 中编写插入排序代码。此代码的输出应该是按升序排列的数字，但出于某种原因我得到 10、4、5、6、7、8、9。任何帮助是极大的赞赏！谢谢！

public class InsertionSort {

    public int Array[] = {10,9,8,7,6,5,4};

    public static void main(String[] args) {
        InsertionSort obj1 = new InsertionSort();
    }

    public InsertionSort() {
        InsertionSortMethod();
        PrintArray();
    }

    public void InsertionSortMethod() {
        for(int j = 2; j < Array.length; j++) {
            int key = Array[j];
            int i = j - 1;
            while(i > 0 && Array[i] > key) {
                Array[i + 1] = Array[i];
                i = i - 1;
            }
            Array[i + 1] = key;
        }   
    }

    public void PrintArray() {
        for(int i = 0; i < Array.length; i++) {
            System.out.println(Array[i]);
        }
    }
}

Answer 1

像这样从 j=1 开始 for 循环 :

for(int j = 1; j < array.length; j++) {

并像这样修改 while 循环条件：

while(i >= 0 && array[i] > key) {

正确的工作代码：

public class InsertionSort {

public int array[] = {10,9,8,7,6,5,4};

public static void main(String[] args) {
    InsertionSort obj = new InsertionSort();
    obj.insertionSortMethod();
    obj.printArray();
}


public void insertionSortMethod() {
    for(int j = 1; j < array.length; j++) {
        int key = array[j];
        int i = j - 1;
        while(i >= 0 && array[i] > key) {
            array[i + 1] = array[i];
            i = i - 1;
    }
        array[i + 1] = key;

    }   
}

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

}

Answer 2

在代码的第三行，即

InsertionSort obj1 = new InsertionSort();

您正在制作 InsertionSort class 的对象，但在您的代码中，它被定义为一个函数，我认为它是一个构造函数，您必须提及 class 以更方便地使用 reader。

除此之外，您从 2 for(int j = 2; j < Array.length; j++) 开始循环为什么这样？你错过了一个元素所以从 1 开始 j :)

Answer 3

感谢大家的回答。我还发现，通过跟踪算法，将算法第 5 行的第二个 'greater than' 符号翻转为 'less than' 符号可以实现按降序工作的技巧。这可能是我正在阅读的书中的错字。再次感谢！

Answer 4

试试这个方法

 public int[] insertionSort(int[] list) {
            int i, j, key, temp;
            for (i = 1; i < list.length; i++) {
                key = list[i];
                j = i - 1;
                while (j >= 0 && key < list[j]) {
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    j--;
                }

            }
            return list;
        }

Answer 5

package com.borntoinnovation.datastructure;

import java.util.Arrays;

public class SortingInsertion {

    public static void main(String[] args) {
        int[] array = new int[] { 4, 3, 2, 20, 12, 1, 5, 6 };

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[i] < array[j]) {
                    int temp = array[i];
                    for (int k = i; k > j; k--) {
                        array[k] = array[k - 1];
                    }
                    array[j] = temp;
                }
            }
            System.out.println(Arrays.toString(array));
        }

    }// end of main()
}

Java 插入排序错误

Error in Java Insertion Sort

java

arrays

sorting

insertion-sort