关于插入排序

算法
Catalogue
  1. 1. 代码（JavaScript 实现）
  2. 2. 算法复杂度

代码（JavaScript 实现）

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
var A = [1, 3, 5, 2, 27, 7, 100, 9, 109, 10, 87, 800, 988, 7665, 83790, 28, 34];
var B = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
/**
 * 插入排序
 * @param  {Array} A [数组]
 * 不返回值，原地进行排序，这样可以有较低的空间复杂度
 */
function insertSort(A) {
  var O = 0;
  if (A[0] > A[1]) {
    var tmp = A[1];
    A[1] = A[0];
    A[0] = tmp;
  }

  for (var i = 2; i <= A.length-1; i++) {
    var end = A[i];
    // 寻找插入位置，根据要升序还是要降序来决定从后向前还是从前向后查找
    if (end > A[i-1]) {
      continue;
    }
    for (var j = i-1; j >= 0; j--) {
      if (((end >= A[j]) && (end <= A[j+1])) || (end < A[0] && (j === 0))) {
        // 开始移动
        for (var k = i; k > j; k--) {
          A[k] = A[k-1];
          O++;
        }

        if ((end < A[0]) && (j === 0)) {
          A[0] = end;
        } else {
          A[j+1] = end;
        }
      }
    }
  }

  console.log(A);
  console.log(O);
}

insertSort(A);
insertSort(B);

算法复杂度

最好的情况，数组已经是升序了，那么时间复杂度是 O(N)。最坏的情况，i 循环 N，内部每个 i 循环 移动 N-i 个元素，复杂度可以达到 O(N2)，感觉不靠谱……

Share