关于Java排序算法-直接插入排序(Insert Sort)

关于Java排序算法-直接插入排序(Insert Sort)

基本思想:当插入第i (i ≥ 1) 个记录时, 前面的A[0], A[1], …, A[i-1]已经排好序。这时, 用A[i]的排序码与A[i-1], A[i-2], …的排序码顺序进行比较, 找到插入位置即将A[i]插入, 原来位置上的记录向后顺移。
过程:首先将待排序序列的第 1 个数据元素看成是一个有序的子序列,然后依次将第 2 个数据元素、第 3 个数据元素、…… 插入到这个有序序列。

public class SortTest {
  public static void main(String[] args) {
    int[] arr = { 21, 25, 49, 25, 22, 8 };
    display("原始数据 : ", arr);
    // 直接插入排序
    insertSort(arr);
    display("排序结果:", arr);
  }


  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 直接插入排序
  private static void insertSort(int[] arr) {
    int i, j, temp;
    for (i = 1; i < arr.length; i++) {
      temp = arr[i];
      j = i - 1;
      while (j >= 0 && temp < arr[j]) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = temp;
    }
  }
}

原始数据 :
21 25 49 25 22 8
排序结果:
8 21 22 25 25 49

发表回复

您的电子邮箱地址不会被公开。