排序算法之直接插入排序（Java）

本人对排序算法理解不深，希望通过动手写一写排序算法的实现，加深印象和理解

算法过程

1. 把待排序数据分为2个区：

• 有序区（初始第1个元素）
• 无序区（初始第2至n个元素）

2. 从无序区取第1个元素x，与有序区最后1个元素y依次往前比较

• 如果y>x，则y往后挪动1个位置，并记录待插入的位置pos
• 直到y<=x或到达有序区第1个元素时，把x插入pos位置

3. 从无序区分别取第2至n元素，重复步奏2

上代码Java

/**
 * 直接插入排序
 */
@Test
public void insertSort() {
    // 待排序数组
    int[] a = { 8, 7, 3, 9, 0, 4, 5, 1, 6, 2 };
    System.out.println("--原始数组：" + arrayToStr(a));
    for (int i = 1; i < a.length; i++) {
        // 无序区待插入元素x
        int x = a[i];
        // 待插入有序区位置pos
        int pos = i;
        // 有序区待比较元素y
        int y;
        // 从后往前依次比较大小（期间保证pos大于0），检查y是否大于x
        while (pos > 0 && (y = a[pos - 1]) > x) {
            // y往后挪动，腾出位置
            a[pos] = y;
            // 更新插入位置
            pos--;
        }
        // 插入x元素到最终位置pos
        a[pos] = x;
        System.out.println("第" + i + "轮结果：" + arrayToStr(a));
    }
    System.out.println("over!");
}

/**
 * 数组拼接成字符串
 */
private String arrayToStr(int[] a) {
    StringBuilder buff = new StringBuilder(a.length * 3);
    for (int t = 0; t < a.length; t++) {
        buff.append(a[t]).append(" ");
    }
    return buff.toString();
}

输出结果及过程分析

-原始数组：8 7 3 9 0 4 5 1 6 2 # 7与8比较8往后挪动1位；最后7插入0位置
第1轮结果：7 8 3 9 0 4 5 1 6 2 # 3与8比较8往后挪动1位；3与7比较7往后挪动1位；最后3插入0位置
第2轮结果：3 7 8 9 0 4 5 1 6 2 # 9与8比较无挪动，over！
第3轮结果：3 7 8 9 0 4 5 1 6 2 # 0与9比较9挪动；0与8、7、3比较均挪动；最后0插入0位置
第4轮结果：0 3 7 8 9 4 5 1 6 2 # 4与9比较，依次类推
第5轮结果：0 3 4 7 8 9 5 1 6 2 
第6轮结果：0 3 4 5 7 8 9 1 6 2 
第7轮结果：0 1 3 4 5 7 8 9 6 2 
第8轮结果：0 1 3 4 5 6 7 8 9 2 
第9轮结果：0 1 2 3 4 5 6 7 8 9 
over!