java 简略插入排序
java 简单插入排序
/*** * 简单插入排序算法练习 * * @author bobo * */ public class InsertSort { /*** * 插入排序的逻辑为:新建一个有序序列,从源数组中挨个挑取数组插入到有序序列的何合适位置 * * @param args */ public static void main(String[] args) { int[] a = { 1, 0, 3, 4, 2, 3, 5, 3, 6, 8, 2 }; show(a); for (int i = 0; i < a.length-1; i++) { insertOne(a, i+1); show(a); } show(a); } /** * 一次插入的方法 * * @param a * 要被插入的有序序列 为提高算法的空间效率 是源数组 * @param i * 要插入的数据的索引 */ private static void insertOne(int[] a, int index) { // 待插入的数据的索引为i则a的有序长度应该是index // 第一层循环的条件中=是哨兵原则,因为index处的值有可能就放在有序序列的队尾 for (int i = 0; i <= index; i++) { if (a[i] >= a[index]) {// 找到插入位置 int tmp = a[index];// 缓存数据 防止被覆盖掉 // 后移i到index-1这些数组的元素,腾出i的位置同时覆盖掉index的位置 // 后移数组元素应该从后面开始 否则会出现覆盖的情况 for (int j = index - 1; j >= i; j--) { a[j + 1] = a[j]; } a[i] = tmp; } } } private static void show(int[] a) { for (int i : a) { System.out.print(i + "\t"); } System.out.println(); } }