使用 Java 的 DSA - 插入排序

概述

插入排序是一种简单的排序算法。此排序算法是基于就地比较的算法，其中取出一个项目，搜索其合适的位置，并将该项目插入到该特定位置，从而增加排序列表。此算法不适用于大型数据集，因为其平均和最坏情况复杂度为 O(n²)，其中 n 是项目数。

伪代码

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
   for i = 1 to length(A) inclusive do:
      /* 选择要插入的值 */
      valueToInsert = A[i]
      holePosition = i
      /*定位要插入元素的孔位置*/
      while holePosition > 0 and A[i-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
      /* 在洞的位置插入数字 */
      A[holePosition] = valueToInsert
   end for
end procedure

演示程序

package com.tutorialspoint.simplesort;

import java.util.Arrays;

public class InsertionSortDemo {
     
   public static void main(String[] args){
      int[] sourceArray = {4,6,3,2,1,9,7};
      System.out.println("Input Array: " 
         + Arrays.toString(sourceArray));
      printline(50);
      System.out.println("Output Array: " 
         + Arrays.toString(insertionSort(sourceArray)));
      printline(50);        
   }    

   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
         System.out.println("=");
   }

   public static int[] insertionSort(int[] intArray){

      int valueToInsert;
      int holePosition;
      // 循环遍历所有数字
      for(int i=1; i < intArray.length; i++){ 
         // 选择要插入的值。
         valueToInsert = intArray[i];
         // 选择要插入数字的孔位置
         holePosition = i;
         // 检查前一个数字是否大于要插入的值
         while (holePosition > 0 && intArray[i-1] > valueToInsert){
            intArray[holePosition] = intArray[holePosition-1];
            holePosition--;
            System.out.println(" item moved :" + intArray[holePosition]);
         }

         if(holePosition!= i){
            System.out.println(" item inserted :" 
               + valueToInsert +", at position :" + holePosition);
            // 在洞的位置插入数字
            intArray[holePosition] = valueToInsert;   
         }

         System.out.println("iteration "+(i) +"#: " 
            + Arrays.toString(intArray));
      }
      return intArray;
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
iteration 1#: [4, 6, 3, 2, 1, 9, 7]
 item moved :6
 item moved :4
 item inserted :3, at position :0
iteration 2#: [3, 4, 6, 2, 1, 9, 7]
 item moved :6
 item moved :4
 item moved :3
 item inserted :2, at position :0
iteration 3#: [2, 3, 4, 6, 1, 9, 7]
 item moved :6
 item moved :4
 item moved :3
 item moved :2
 item inserted :1, at position :0
iteration 4#: [1, 2, 3, 4, 6, 9, 7]
iteration 5#: [1, 2, 3, 4, 6, 9, 7]
 item moved :9
 item moved :6
 item inserted :7, at position :4
iteration 6#: [1, 2, 3, 4, 7, 6, 9]
Output Array: [1, 2, 3, 4, 7, 6, 9]
==================================================