算法之排序-插入排序

文章目录
  1. 1. 算法描述
  2. 2. 命题B
  3. 3. 命题C
  4. 4. 特点
  5. 5. 代码

算法描述

通常人们整理桥牌的方法是一张一张的来，将每一张插入到其他已经有序额牌中的适当位置。在计算机实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但他们的最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

和选择排序不同的是，插入排序所需要的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或者接近有序）的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快的多。

命题B

对于随机排列长度为N且主键不重复的数组，平均情况下插入排序需要 ~ N²/4 次比较以及 ~ N²/4 次交换。最坏情况下需要 ~ N²/2 次比较和 ~ N²/2 次交换，最好情况下需要 N-1次比较和0次交换。

命题C

插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

特点

插入排序对于部分有序的数组十分高效，也适合小规模数组。

几种典型的部分有序数组：

  • 数组中每个元素距离它的最终位置都不远
  • 一个有序的大数组接一个小数组
  • 数组中只有几个元素的位置不正确

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Insertion {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N = a.length;
        for (int i = 0; i < N; i++) {
            //将a[i]插入到a[i-1],a[i-2],a[i-3]...之中
            for (int j = i; j > 0; j--) {
                if (less(a[j], a[j - 1])) {
                    exchange(a, j, j - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Character[] a = {'S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
        sort(a);
        if (isSorted(a)) {
            show(a);
        }
    }
    // A E E L M O P R S T X 
}