数据结构与算法-直接插入排序-蒲公英云

数据结构与算法-直接插入排序

以你之姓@ 2022-04-08 10:21 346阅读 0赞

概要

- - 基本概念
  - java代码实现
  - 图示执行过程
  - 时间复杂度分析

基本概念

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表。

java代码实现

/* 声明待排序数组 */
int[] a = {
    9,1,5,8,3,7,4,6,2};
int i,j;
int flag; 
for (i = 1; i < a.length; i++) {
     flag = a[i];    /* 设置哨兵（当前记录） */
     if (a[i] < a[i-1]) {
     /* 当前关键字小于前一个关键字，需要将当前记录往前插入 */
    for (j = i-1; j >= 0 && a[j] > flag; j--) {
     /* 循环遍历当前关键字之前的所有关键字，并与哨兵比较，若大于哨兵，则记录后移 */
         a[j+1] = a[j];    /* 记录后移 */
    }
        //伪代码 a[j] = flag; 因为j循环最后执行j--，故这边j需+1
    a[j+1] = flag;    /* 将哨兵插入正确位置 */
      }
}

图示执行过程

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70

时间复杂度分析

最好的情况，也就是待排序的表本身就是有序的，比较次数为n-1次，因为没有移动的记录，故时间复杂度为O(n)；
最坏的情况，即待排序表是逆序的，此时比较次数为2+3+···+n=(n+2)(n-1)/2次，而记录移动次数也达到最大值2+3+···+n=(n+2)(n-1)/2次，如果排序记录是随机的，那么根据概相同的原则，平均比较和移动次数约为n2/4次，故时间复杂度为O(n2)；
因此，直接插入排序时间复杂度为O(n2)，但分析可知性能要比冒泡排序和简单选择排序好一些。