我是否在 java 中正确实施了插入排序？

Question

我了解了插入排序，我们可以通过多种方式实现这种排序，我对此 post 的唯一期望是我的实现是否可以被视为插入排序的实现之一？

  package com.tech.kj.dp;

class InsertionSort1 {
  
  public static void main(String[] args) {
    
   int[] array= {20,54,-15,-9,0,45,2,11};
    
    
    for(int index = 1; index < array.length; index++){
     
      int nextElement = array[index];
      for(int i=0;i<index;i++){
        int sorted=array[i];
        if(nextElement<sorted){
          swap(array,index,i);
        }
      }
    }
    show(array);
  }
  
  public static void swap(int[] array,int i,int j){
    if(i==j){
      return;
    }
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  
  public static void show(int[] array){
    for(int i=0;i<array.length;i++){
        System.out.print(array[i]+"\t");
    }
    System.out.println();
  }
  
}

Answer 1

我相信您的代码给出了正确的结果，正确排序。它并不完全按照我理解的方式进行插入排序。而且我相信它正在做比必要更多的交换。

示例未排序数组：[5, 7, 2].

您的代码第一次通过外循环检查 7 是否不小于 5，因此不应交换这些数字。

下次你第一次检查 2 是否小于 5 时，交换它们，得到 [2, 7, 5]。 nextElement 仍然是 2，所以接下来因为 2 也小于 7，所以你交换 7 和 5。虽然它确实给出了正确的结果，但正如我所说，它似乎不太合逻辑，并且作为 reader 我很难说服自己这是正确的。

取而代之的是我记得理解插入排序的方式：当你找到2的正确位置时（通过确定它小于5），你应该将它复制出数组，将7和5推一个放在右边，然后在 5 之前的位置（索引 0）插入 2（因此称为插入排序）。

我是否在 java 中正确实施了插入排序？

am I implemented correctly Insertion sort in java?

java

sorting

algorithm

data-structures