读书笔记-《数据结构与算法》-摘要4[插入排序]-Toy模板网

这篇具有很好参考价值的文章主要介绍了读书笔记-《数据结构与算法》-摘要4[插入排序]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

插入排序

核心：通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历)，找到相应位置并插入。实现上通常使用in-place排序(需用到O(1)的额外空间)

从第一个元素开始，该元素可认为已排序
取下一个元素，对已排序数组从后往前扫描
若从排序数组中取出的元素大于新元素，则移至下一位置
重复步骤3，直至找到已排序元素小于或等于新元素的位置
插入新元素至该位置
重复2~5

读书笔记-《数据结构与算法》-摘要4[插入排序],读书笔记,排序算法,算法

public class InsertionSort {
    public static void main(String[] args) {
        int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        insertionSort(unsortedArray);
        System.out.println("After sort: ");
        for (int item : unsortedArray) {
            System.out.print(item + " ");
        }
    }

    public static void insertionSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {
            int index = i, array_i = array[i];
            while (index > 0 && array[index - 1] > array_i) {
                array[index] = array[index - 1];
                index -= 1;
            }
            array[index] = array_i;

            /* print sort process */
            for (int item : array) {
                System.out.print(item + " ");
            }
            System.out.println();
        }
    }
}

输出：

6 5 3 1 8 7 2 4 
5 6 3 1 8 7 2 4 
3 5 6 1 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 7 8 2 4 
1 2 3 5 6 7 8 4 
1 2 3 4 5 6 7 8 
After sort: 
1 2 3 4 5 6 7 8