插入排序详解

插入排序是一种比较直观的排序方式。插入排序：把未排序的数组中第一个元素当作一个有序的数组，取剩余未排序的第一个元素，和有序数组的最后一个元素比较，如果小于最后一个元素，最后一个元素后移一位，直到找到合适的位置插入。循环执行上述操作，直达未排序的元素执行完。（这个类似于打牌，洗牌）

插入排序还可以进行一些优化（插入操作过程中，进行二分查找对比，进行插入操作）

1.算法步骤

1. 数组的第一个元素当作一个有序的数组，把第二个元素到最后一个元素当作未排序的数组。
2. 从未排序数组中取出首个元素A(剩余元素成为新的未排序数组),逆向循环（从尾部到首部）从有序数组取出元素B进行对比，如果A小于元素B，元素B向后移一位。（如果小于B，则把元素A插入到B元素后的位置）。
3. 循环执行步骤2，执行完未排序数组。

2.算法演示流程

3.算法代码

                function insertSort(arr){
                    var len = arr.length;
                    var preIndex, current;
                    for(var i = 1, i < len - 1; i++){
                        preIndex = i - 1;
                        current = arr[i];

                        while(preIndex >= 0 && arr[preIndex] > current){
                            arr[preIndex + 1] = arr[preIndex];
                            preIndex--;
                        }
                        arr[preIndex + 1] = current;
                    }

                    return arr;
                }