Hello World

吞风吻雨葬落日 欺山赶海踏雪径

0%

插入排序

发表于 更新于 分类于

插入排序

算法原理

设有一组关键字｛K1， K2，…， Kn｝；排序开始就认为 K1 是一个有序序列；让 K2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 Kn 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘
[5, 6]   3   1   8   7   2   4
↑        │
└────────┘
[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘
[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘
[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘
[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘
[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘
 
[1, 2, 3, 4, 5, 6, 7, 8]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insertDirect(int[] a)
{
    //n-1次扫描，依次向前插入n-1个元素
    for(int i=1;i<a.length;i++)
    {
        //每趟将a[i]插入到前面的排序子序列中
        int temp=a[i];
        int j=i-1 ;
        for(;j>=0&&temp<a[j];j--){
            //将前面较大的元素向后移动
            a[j+1]=a[j];
        }
        //temp值到达插入位置
        a[j+1]=temp;
    }
}

分析

时间复杂度：

  1. 最好情况：O(n)
  2. 平均情况：O(n^2)
  3. 最坏情况：O(n^2)

空间复杂度：O(1)

稳定性：稳定(相同元素的相对位置不会改变)

适用场景

  • 当n <= 50时，适合适用直接插入排序和简单选择排序，如果元素包含的内容过大，就不适合直接插入排序，因为直接插入排序需要移动元素的次数比较多.
  • 当数组基本有序的情况下适合使用直接插入排序和冒泡排序，它们在基本有序的情况下排序的时间复杂度接近O(n).

二分插入排序

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

二分插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 二分查找 找到tmp应该在的位置
private int binarySearch(int array[], int low, int high, int temp) {
    while (low <= high) {
        //中间指针
        int mid = (low + high) / 2;
        //中间的值小于指定值，且中间位置+1的值大于等于指定值
        //这个mid+1的位置就是要放置的位置了 直接返回mid+1
        if (array[mid] < temp && temp <= array[mid + 1]) {
            return (mid + 1);
        }
        //中间位置的值小于指定值，继续搜索后半部分
        //后半部分就是mid+1 => high
        if (array[mid] < temp) {
            low = mid + 1;
        } else {
            //否则继续前半部分 low => mid-1
            high = mid - 1;
        }
    }

    //否则就是最高位置
    return high;
}

//二分插入排序，减少比较次数，但是移动次数没有减少
private void binarySort(int array[]) {
    int k = 0;
    // 1->n 趟的排序
    for (int i = 1; i < array.length; i++) {
        //先取出这个基准值 temp（向后移动的时候会被覆盖的）
        int temp = array[i];
        //如果当前位置的值大于第一个
        //需要找到合适的位置
        if (array[i] >= array[0]) {
            //print(array,0+"->"+i+" find "+temp +" pos "+k+" in ");
            //二分查找快速找到位置k
            k = binarySearch(array, 0, i, temp);
        }else {
            //否则放在第一个
            k=0;
        }

        //把 k->i的元素全部向后移动一位
        for (int j = i; j > k; j--) {
            array[j] = array[j - 1];
        }
        //把值放入k位置
        array[k] = temp;
    }
}