【经典排序算法】3. 插入排序

对顺序性强的数据，插入排序就比较快（最好情况O(n)）

代码如下：

public class Main {

    public static void main(String[] args) {
        int[] arr = {3, 3, 5, 6, 2, 1};
        arrPrint(arr);
        InsertSort(arr);
        arrPrint(arr);
    }

    // 插入排序
    // 该算法将遍历数arr[i]之前所有比arr[i]大的数整体右移，腾出的位置放置arr[i]。
    // 只要遍历从左到右遍历数组一遍，即可完成整个排序。
    // 一级for循环从第二个元素开始遍历，索引为i。arr[i]即为待排序元素，
    // 将其保存为temp。之后创建新索引j，将其初始化为j=i，并使其向左遍历数组。
    // 当arr[j - 1]比temp=arr[i]大时，元素直接右移（arr[j]=arr[j-1]），
    // 指针左移一位j--，继续判断。直到arr[j - 1]不比temp=arr[i]大为止。
    // 此时就让temp放置在arr[j]位置，完成一次元素的排序。for循环结束则排序结束。
    private static void InsertSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int temp = arr[i];
            int j = i;
            while (j > 0 && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                j--;
            }
            if (j != i) {
                arr[j] = temp;
            }
        }
    }

    // 辅助函数：将int[] 打印出来
    private static void arrPrint(int[] arr) {
        StringBuilder str = new StringBuilder();
        str.append("[");
        for (int v : arr) {
            str.append(v + ", ");
        }
        str.delete(str.length() - 2, str.length());
        str.append("]");
        System.out.println(str.toString());
    }
}

实例动画演示如下：