排序算法之插入排序-蒲公英云

排序算法之插入排序

[插入排序-普通插入排序]

1.算法思想

将元素a视为基序列，遍历数组将元素a右边的元素依次插入序列中，找到比自己小的数置于其后，保证序列一直处于已排序的状态。

2.流程解析

将元素a作为基序列
向序列中插入元素b，比较a、b
- 若b < a，将a向后移动一个位置，b赋值给a，序列：[b、a]
- 若b > a，则不变
插入元素c，比较c与a、b
- 若c < b < a，将b后移，a后移，c前置，序列：[c、b、a]
- 若b < c < a，将b后移，a不变，c置于a后，序列：[b、c、a]
插入元素d，以此类推

3.动态排序图

4.代码实现

public static void insertionSort(int[] array){ 
        //定义insert，用于存放取出元素
        int insert;
        for (int i = 0; i < array.length - 1; i++) { 
            //取出元素值
            insert= array[i + 1];
            //待比较元素下标
            int preIndex = i;
            while(preIndex >= 0 && array[preIndex] > insert){ 
                //待比较元素>取出元素，将待比较元素后移一个位置
                array[preIndex + 1] = array[preIndex];
                //待比较下标-1，继续与取出元素比较
                preIndex--;
            }
            //待比较元素<取出元素。将取出元素值放在该待比较元素的后一个位置
            array[preIndex + 1] = insert;
        }
    }
    public static void main(String[] args) { 
        int[] array = { 6 , 1 , 3 , 7 , 2 , 9 , 10 , 8 , 5 , 4};
        System.out.println("排序前Array:"+ Arrays.toString(array));
        insertionSort(array);
        System.out.println("排序后Array:"+ Arrays.toString(array));
        /* * 排序前Array:[6, 1, 3, 7, 2, 9, 10, 8, 5, 4] * 排序后Array:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] */
    }