使用插入排序对数组进行排序

Question

我应该取一个数字数组：{51, 63, 48, 98, 75, 63, 92, 30, 32, 32, 36, 89, 4, 76, 73, 90, 64, 99, 36, 96} 并将它们从低到高排序，然后从高到低排序。

当我尝试从最高到最低打印时，它使第一个输出相同。有人在我的代码中看到任何错误吗？

package l7c14sort;

import java.util.Arrays;

public class L7C14Sort {

public static void main(String a[]){
    int[] arr1 = {51, 63, 48, 98, 75, 63, 92, 30, 32, 32, 36, 89, 4, 76, 73, 90, 64, 99, 36, 96};


    int[] arr2 = doInsertionSort(arr1);

    int[] arr3 = doInsertionSortAgain(arr1);

    System.out.println("Original input: "+Arrays.toString(arr1)+"\n");
    System.out.println("Lowest to highest:\n");


    for(int i:arr2)
    {
        System.out.print(i);
        System.out.print(", ");

    }
    System.out.println("\n\n");
    System.out.println("Highest to lowest:\n");

    for(int k:arr3)
    {
        System.out.print(k);
        System.out.print(", ");

    }

    System.out.println("\n");
}

public static int[] doInsertionSort(int[] input){

    int temp;
    for (int i = 1; i < input.length; i++) {
        for(int j = i ; j > 0 ; j--){
            if(input[j] < input[j-1]){
                temp = input[j];
                input[j] = input[j-1];
                input[j-1] = temp;

            }
        }
    }
    return input;
}

public static int[] doInsertionSortAgain(int[] input2){

    int temp2;
    for (int k = 1; k < input2.length; k++) {
        for(int j = k ; j > 0 ; j--){
            if(input2[j] > input2[j-1]){
                temp2 = input2[j];
                input2[j] = input2[j-1];
                input2[j-1] = temp2;

            }
        }
    }

    return input2;
}

}

输出：

Original input: [99, 98, 96, 92, 90, 89, 76, 75, 73, 64, 63, 63, 51, 
                 48, 36, 36, 32, 32, 30, 4]

从最高到最低：

99, 98, 96, 92, 90, 89, 76, 75, 73, 64, 63, 63, 51, 48, 36, 36, 32, 32, 30, 4,

从最低到最高：

4,30,32,32,36,36,48,51,63,63,64,73,75,76,89,90,92,96,98,99

Answer 1

好消息：您的算法运行良好。

在Java中，数组是按引用传递的，而不是按值传递的。这意味着当您设置 int[] arr2 = doInsertionSort(arr1); 时，数组 arr2 被设置为您的 doInsertionSort 方法的结果，returns 它的 input 参数之后排序它。基本上，arr1、arr2、arr3、input 和 input2 都指向同一个数组。

您有两个简单的选项来修复您正在打印的事实：

重构main()以便使用一个数组：打印它的内容，从低到高排序，再次打印它的内容，从高到低排序，然后再次打印它的内容。（如果这是课程作业，这可能是您的讲师打算让您做的。）
复制要操作的 input 参数。您可以像这样使用 System.arraycopy() 执行此操作：

int[] myArray; System.arraycopy(input, 0, myArray, 0, input.length );

然后，对于选项 2，您需要编辑您的方法，以便每隔一次使用 myArray 而不是 input input.

请注意，您不需要调用变量 input2、temp2 等。就像 i、j 和 k 超出范围并在 for 循环结束后被遗忘，你的变量 input 和 temp 在你声明它们的块之外没有任何意义。

希望对您有所帮助！

Answer 2

你得到了相同的结果，因为数组是可变的。由于以下代码，输入数组发生变异并打印其最终值。（从最高到最低）。

int[] arr2 = doInsertionSort(arr1);

int[] arr3 = doInsertionSortAgain(arr1);

如果您像这样组织代码：

public static void main(String a[]) {
int[] arr1 = {51, 63, 48, 98, 75, 63, 92, 30, 32, 32, 36, 89, 4, 76, 73, 90, 64, 99, 36, 96};

System.out.println("Original input: " + Arrays.toString(arr1) + "\n");
System.out.println("Lowest to highest:\n");

int[] arr2 = doInsertionSort(arr1);


for (int i : arr2) {
  System.out.print(i);
  System.out.print(", ");

}
System.out.println("\n\n");
System.out.println("Highest to lowest:\n");

int[] arr3 = doInsertionSortAgain(arr1);

for (int k : arr3) {
  System.out.print(k);
  System.out.print(", ");

}
System.out.println("\n");

}

您将获得：

Original input: [51, 63, 48, 98, 75, 63, 92, 30, 32, 32, 36, 89, 4, 76, 73, 90, 64, 99, 36, 96]

Lowest to highest: 4, 30, 32, 32, 36, 36, 48, 51, 63, 63, 64, 73, 75, 76, 89, 90, 92, 96, 98, 99,

Highest to lowest: 99, 98, 96, 92, 90, 89, 76, 75, 73, 64, 63, 63, 51, 48, 36, 36, 32, 32, 30, 4,

使用插入排序对数组进行排序

Using Insertion Sort to sort an array

java

arrays

sorting

insertion-sort

insertion