Java 插入排序与优化

插入排序思想

将数组分为两个部分，排序部分和未排序部分。

每一轮遍历从未排序部分取出第一个元素，插入到排序部分的对应位置。

重复以上过程，直到整个数组有序。

代码实现

为了能更好地展示冒泡排序的主要思想，我将数据准备工作定义在 main() 方法中。

public static void main(String[] args) {
    int[] nums = {5,9,7,4,6,1,3,2,8};
    System.out.println("排序前 " + Arrays.toString(nums));
    insertionSort(nums);
    System.out.println("排序后 " + Arrays.toString(nums));
}

private static void insertionSort(int[] nums) {

}

完成插入排序的代码：

private static void insertionSort(int[] nums) {
    // i 代表待插入元素的位置，假设第一个元素已经排序完成，索引从 1 开始
    for (int i = 1; i < nums.length; i++) {
        // 待插入的元素值
        int tmp = nums[i];
        // 已排序区域的最后一个元素位置
        int j = i - 1;
        // 寻找 tmp 元素应该放到已排序区域的位置
        while (j >= 0){
            // 如果待插入元素比已排序区域的最后一个元素还小
            if(tmp < nums[j]){
                // 把最后一个位置让出来
                nums[j + 1] = nums[j];
            }else {
                // 说明最后指向的最后一个元素比待插入元素小，可以结束比较
                break;
            }
            j--;
        }
        // 待插入的元素放到已排序区域的合适位置
        nums[j+1] = tmp;
        System.out.println(Arrays.toString(nums));
    }
}

为了更好观察内部变化，每轮遍历后，打印了当时的数组情况。

优化思路

当待插入元素 tmp 在寻找自己应该插入的位置时，当遇到比自己元素小（或者相等）时，就结束遍历。

插入元素可以使用移动元素，而不是交换元素。

插入排序与选择排序

| — | — | — |
| 维度 | 插入排序 | 选择排序 |
| 时间复杂度 | n² | n² |
|效率| 相对效率高 | 相对效率低|
|稳定性| 稳定 | 不稳定 |

为什么插入排序比选择排序效率高？

插入排序使用的是移动元素，选择排序是交换元素，移动元素比交换元素效率高。

移动元素的核心代码：

nums[j+1] = nums[j];

交换元素的核心代码：

int tmp = nums[n];
nums[n] = nums[m];
nums[m] = tmp;

很明显，移动元素的步骤要少于交换元素。