算法 - 插入排序（Insertion Sort）

2019-02-13 1 分钟阅读 ARTS-A

极客时间 - 数据结构与算法之美 - 11 | 排序（上）

算法描述：

a为待排序数组，n为数组长度
i为元素下标，a[ < i]的元素都是已排序好的，a[ >= i]的元素都是还未排序的。即把a分为两个区间：已排序区间和未排序区间。
循环 n - 1 次，初始i = 1：
- 取v = a[i]，与a[i - 1 … 0]的元素比较（注意是从后往前的顺序），记这个元素为a[j]
- 若v < a[j]，则将a[j]往后移动
- 若v >= a[j]，则将v插入到a[j+1]的位置，i++
- 直到 i = n 为止

速记法：把这个想象成整理手中的扑克牌，取第二张牌往前插，第三张牌往前插，第四张牌往前插，……

算法本质：已排序区间初始为数组的第一个元素，然后不停将未排序区间的元素插入到已排序区间的合适的位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

版权

CC BY-NC-ND 4.0

评论