插入排序

阅读量: 483 编辑

插入排序 - insertionSort

一、算法步骤

  • 1、将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

  • 2、从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。

二、Java代码

//插入排序:正序排列
public static int[] insertionSort(int[] array) {
    if (array.length == 0)
        return array;

    int curItem;

    for (int i = 0; i < array.length - 1; i++) {
        curItem = array[i + 1];//依次遍历目标元素

        int preIndex = i;
        //依次向前找(合适的位置),并数据向后移动,从而这个空出合适的位置
        while (preIndex >= 0 && array[preIndex] > curItem) {
            array[preIndex + 1] = array[preIndex];
            preIndex--;
        }

		//将目标元素插入到空出来的位置上
        array[preIndex + 1] = curItem;
    }

    return array;
}

三、代码总结

插入排序,就是依次遍历元素(目标),并向前找到合适的位置插入。

  • 双重循环:外循环就是依次遍历目标,内循环向前找到合适的位置(并空出来)

  • 将目标元素插入到空出来的位置上

苏ICP备13052010号-3
©2022 南京匠成信息科技有限公司