基本思想:当插入第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