简单算法之插入排序

有一群人，假设每个人的身高都不同，现在需要根据他们的身高由低到高进行排序。相信每个人都会很容易完成这个任务。方法不一，每个人都会选择自己的方法。每种方法的效率不尽相同，但都有成效。

一种方法是这样的：首先让这群人随意排成一队，然后第一个人站着不动，第二个人和自己的前一位比较（也就是第一位）。如果第二个人比前面的人矮，就与前面的人换位置，如果比前面的人高或相同，则站着不动。

第三个人和第二个人一样，只不过可能会比第二个人多一步。第三个人先与前面的人比较，如果他比前面的人矮就与前面的互换位置，换了位置后再与此时前面的人比较，直到前面的人比自己矮或前面没有任何人了。

这种方法抽象出来，就是编程中的插入排序。以 js 代码为例，具体代码如下：

1

let arr = [1,11,7,3,5,8,4,9]
for(let i = 1;i < arr.length;i++){
  let store = arr[i];
   let j = i-1;
  while(j > 0 && arr[j] > store) {
    let mid = arr[j+1];
     arr[j+1] = arr[j];
     arr[j] = mid;
    j--;
    }
}
console.log(...arr);

2

  let arr = [1,11,7,3,5,8,4,9]
 for(let i = 1;i < arr.length;i++){
 let store = arr[i];
 let j = i-1;
 while(j > 0 && arr[j] > store) {
     arr[j+1] = arr[j];
     j--;
 }
 arr[j+1] = store;
}
console.log(...arr);
// 1 3 4 5 7 8 9 11

上面两种方法思路是相似的，只不过数字交换的方式有点差别。