Java进阶ch2 插入排序

插入排序，对未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入。

插入排序类似扑克牌插牌。

如果输入数组已经排好序，插入排序出现最佳情况。如果数组逆序排序，出现最坏情况，最坏情况、平均情况复杂度为n²。

public void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 需要插入的数，默认从无序段元素arr[1]开始插入有序段
        int insertVal = arr[i];
        // 插入位置下标
        int index = i - 1;
        // 如果需要插入的数小于arr[index]，arr[index]向后移动一步，移除插入位置
        while (index >= 0 && insertVal < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = insertVal;
    }
}

本文作者： Yao Zhu
发布时间： 2019-11-17
最后更新： 2019-12-08
本文链接： https://juoyo.github.io/posts/b4185157.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信