插入排序

  算法   4分钟   338浏览   0评论

1.插入排序概念

将数组分为两个区域,排序区域和未排序区域,每一轮从未排序的区域中选取第一个元素,插入到排序区域。(需保证顺序)
重复以上步骤,直至数组有序。
举个例子:

int[] a = {9, 3, 7, 2, 5, 8, 1, 4};

刚开始选取第一个元素即9为排序区
第一轮选取到3,因为3<9,故3插入到9前面,此时排序区为{3,9}
第二轮选取到7,因为3<7<9,故插入至它们中间,此时排序区为{3,7,9};
......
以此类推

2.编程思路

1. 定义 i 表示待插入元素的索引,从1开始
2. 定义 t 表示待插入的元素值
3. 定义 j 表示已排序区域的最后一个元素索引
4. 如果待插入元素小于排序区域中的最后一个,将原最后一个往后移一位

3.代码实现

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/15 13:21
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
        insert(a);
    }

    private static void insert(int[] a) {
        // i 表示待插入元素的索引,从1开始
        for (int i = 1; i < a.length; i++) {
            // t 表示待插入的元素值
            int t = a[i];
            // j 表示已排序区域的最后一个元素索引
            int j = i - 1;
            while (j >= 0) {
                if (t < a[j]) {
                    // 待插入元素小于排序区域中的最后一个,将原最后一个往后移一位
                    a[j + 1] = a[j];
                } else {
                    // 退出循环,减少比较次数
                    break;
                }
                j--;
            }
            a[j + 1] = t;
            System.out.println(Arrays.toString(a));
        }
    }
}

输出结果:
[3, 9, 7, 2, 5, 8, 1, 4]
[3, 7, 9, 2, 5, 8, 1, 4]
[2, 3, 7, 9, 5, 8, 1, 4]
[2, 3, 5, 7, 9, 8, 1, 4]
[2, 3, 5, 7, 8, 9, 1, 4]
[1, 2, 3, 5, 7, 8, 9, 4]
[1, 2, 3, 4, 5, 7, 8, 9]

4.优化

优化方式:

  1. 待插入元素进行比较时,遇到比自己小的元素,就代表找到了插入位置,无需进行后续比较
  2. 插入时可以直接移动元素,而不是交换元素
    上述代码已经进行优化。

5.插入排序与选择排序的区别

  1. 二者时间复杂度都是O(n²)
  2. 大部分情况下,插入都优于选择
  3. 有序集合插入排序的时间复杂度为O(n)
    4. 插入属于稳定排序算法,选择属于不稳定排序。

稳定排序与不稳定排序的区别?
https://www.hqxiaozou.top/post/9ucgtpg6hga

6.例题演示

如果你觉得文章对你有帮助,那就请作者喝杯咖啡吧☕
微信
支付宝
  0 条评论