插入排序

视频教程

建议快进播放。

• 2-7 插入排序（05:57） (opens new window)

插入排序的基本思想

插入排序每一次将一个元素 插入 到它前面的有序数组中。实际上有两种插入的方式：

• 逐个交换：待插入元素逐个交换到前面

• 先暂存再后移：先暂存待插入元素，然后前面比暂存元素严格大的后移

其实这种插入方式更像插入排序本来的样子。《算法导论》上的图更形象。

插入排序写法一：基于交换

参考代码：

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 把 nums[i] 插入有序数组 nums[0..i - 1]
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                // 注意：前面的数严格大于后面的数才交换
                if (nums[j - 1] > nums[j]) {
                    swap(nums, j, j - 1);
                } else {
                    break;
                }
            }
        }
        return nums;
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

注意：「插入排序」可以提前终止内层循环，体现在 nums[j - 1] > temp 不满足时。

复杂度分析：

• 时间复杂度：，这里 是数组的长度；
• 空间复杂度：，使用到常数个临时变量。

参考资料

• 《算法 4》英文网站 (opens new window)

---

作者：liweiwei1419 链接：https://suanfa8.com/basic-sorting-algorithm/insertion/introduction 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。