温故之 “插入排序”

[whkl]

概念：将一个数据插入已经排好序的有序数组中，从而得到一个新的多一个数据的有序数组。

概念理解~~

将要排序的是一个乱的数组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;
    }