插入排序

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>插入排序</title>
</head>

<body>

</body>
<script>
  function insertion_sort(A) {
    for (let i = 1; i < A.length; i++) {
      insert(A, i, A[i])
    }
  }
  function insert(A, i, x) {
    let p = i - 1;
    while (p >= 0 && A[p] > x) {
      A[p + 1] = A[p]
      p--
    }
    A[p + 1] = x
  }
  const A = [5, 8, 1, 3, 2, 4, 9]
  insertion_sort(A)
  console.log(A)
</script>

</html>

过程如下：

【5, 8, 1, 3, 2, 4, 9】
第一次循环：
i=1;x=8;
insert 方法里面：
p = 0;A[1] = 8 不符合跳出循环 A【0】= 5
结果:
[5,8,1,3,2,4,9]

第二次循环：
i=2;x=1
insert 方法里面：
（1）p = 1 大于 0, A[1] = 8 大于 1符合条件
A【1+1】 = A【2】 = 8
所以 [5，1, 8 ,3, 2, 4, 9] ,p=0
(2) p = 0 大于等于 0，A【0】大于 1符合条件
A【0+1】=A【0]
所以 1 和 5 调换顺序
A【1，5，8，3，2，4，8】 p= -1
(3)p=-1 跳出循环
得到一个新数组 A【1，5，8，3，2，4，8】

第三次循环：
i=3;x=3
insert 方法里面：
(1)p=2;A[2]=8 大于 x 符合条件进行循环
A【3】 = A【2】 = 8 得到数组 A【1，5，3，8，2，4，8】 p=1
(2) p= 1,A[1] = 5 大于 x 符合条件进行循环
A[2] = A[1] = 5 , A[1] = 3
得到数组 A【1，3 ，5， 8，2，4，8】 p= 0
(3) p = 0; A[0] = 1 小于 3 不符合条件
跳出循环

上面3个步骤得到新数组
A【1，3 ，5， 8，2，4，8】

所以依次循环第 4， 5，6，7。。。。。。。次得到一个有序数组
[1, 8, 1, 2, 2, 4, 9]