03 sort原理-插入排序

sort方法在chrome的V8引擎里有两种排序方法：
1、插入排序（数组.length<10）；
2、快速排序（数组.length>10）；

插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述：

一般来说，插入排序都采用 in-place 在数组上实现：

1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。

动图演示：

1230971-20190606093850556-1940489422.gif

代码实现：

            const insertSort=arr=>{
                for(let i=1;i<arr.length;i++){
                    let cur=arr[i]; //拿出来的数据
                    let preIndex=i-1;   //拿出来的数据前面的那个数据的索引
                    
                    while(arr[preIndex]>cur){
                        arr[preIndex+1]=arr[preIndex];
                        preIndex--;
                    }
                    
                    arr[preIndex+1]=cur;
                }
                return arr;
            };
            const arr=[12,34,9,22,57];
            console.log(insertSort(arr));

代码分析：

1、先声明一个函数insertSort，接受一个参数arr,就是我们需要排序的数组。
2、在函数里添加一个循环，默认从 i = 1 开始比，因为只有从i = 1开始，左边才有数据。
3、在做循环的时候，我必须拿出一个当前数据 cur,而拿出的数据为cur=arr[i];
4、在第三步，我们拿出来的数据是为了和前面的一个数据做对比，而前面的一个数据的下标为preIndex=i-1;
5、既然我们拿到了当前数据前面的数据，就可以进行比较了，如果只是这样比较，我们只能进行一次比较，所以我们给它添加一个while循环，每比较一次就preIndex--,这样就可以一直向前比较了。
6、给while循环一个执行条件arr[preIndex]>cur,如果前面的一个数据arr[preIndex]大于当前数据cur,把前面的数据，放在当前数据的位置arr[preIndex+1]=arr[preIndex];
7、当while循环停止后，在把拿出来的当前数据cur,放到arr[preIndex+1]这里，之所以'preIndex+1',是因为while循环停止后preIndex--了；
8、for循环结束后，返回数组arr。