溫故之 “插入排序”

概念：將一個數據插入已經排好序的有序數組中，從而得到一個新的多一個數據的有序數組。

概念理解~~

將要排序的是一個亂的數組int[] arrays = {3, 2, 1, 3, 3};
在未知道數組元素的情況下，我們只能把數組的第一個元素作為已經排好序的有序數據，也就是說，把{3}看成是已經排好序的有序數據

• 第一趟排序：
  用數組的第二個數與第一個數(看成是已有序的數組)比較

1. 如果比第一個數大就不用管
2. 如果比第一個數小，將第一個數往后退一步，將第二個數插入第一個數去

• 第二趟排序：
  用數組的第三個數與已是有序的數組{2,3}(剛才在第一趟排出來的結果)比較

1. 如果比第二個數字大就不用管
2. 如果比第二個數字小，就跟第一個數比較，如果比第一個數大，那么將第三個數字插入第二個位置，如果比第一個數字小，那么第一位數將后退一步，將第三個數插入第一位

• 以此類推排序完整個數組

  轉換成代碼前的簡單理解
  1 假定第一個元素是最小值，
  2 從第二個元素開始，往該元素前面的序列比較，
  3 如果后一個元素比前一個元素小，則交換位置

    function insersort (arr) {for(var i=1;i<arr.length-1; i++) { // 從第二個數開始取for(var j=i; j>0; j--) {  // 依次和前面的數做比較if(arr[j]<arr[j-1]) {var k = arr[j];arr[j] =arr[j-1];arr[j-1] = k;}}}return arr;}