忙了一段时间
上一次说完了选择排序，那么继续往下走，本次我们来理解插入排序算法
废话少说，进入正题
如有误，辛苦指正
背景介绍
（Insertion Sort），一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到
的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用
，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行
。 ---插入排序算法
核心特点
- 默认选出待排序数组第一个元素当做一个有序的序列
- 其次依次从待排序数组中抽取元素，依次和有序数列从后往前想比较。
- 当发现前面的元素比当前准备插入的元素大/小时，有序数列元素后移一位，再次比较直到当前插入元素比当前比较的元素小/大时，比较结束，插入此位置
- 重复步骤3即可
举个例子
[ 1, 5, 4, 3, 6, 2, 7 ]
1、先将第一个元素1抽离出来当做一个有序数组得到两个数组
[1]
[ 5, 4, 3, 6, 2, 7 ]
2、再抽出第一个数和有序数组相比较，即5和1比较，发现5大于1，那么直接将5放在1的后面即可，得到
[ 1, 5 ]
[ 4, 3, 6, 2, 7 ]
3、再次取出4和有序数组比较，4 比5小，那么5后移一位数组变成[1, 待插入, 5],再次将4和1比较，发现4 大于 1 那么说明此时 4 插入到1 和 5 之间即可，得到
[ 1, 4 , 5 ]
[ 3, 6, 2, 7 ]
4、依次类推...
此时，我们已经将元素一个一个以“插入”的形式将整个数组排序完成
老规矩，理论加实践 go！
代码示例
1、我们创建一个排序方法，并接受一个参数，就是我们需要排序的数组
function insertionSort( _array ){
}
2、然后我们开始先获取数组的第一个元素，并将它当做有序数组
function insertionSort( _array ){
//取出第一个元素，并当做有序数组
var _sortArray = [ _arr.shift() ];
}
3、根据特点中的，依次取出待排序数组中的第一个元素，和有序数组作比较，直到待排序数组元素比较完毕，如果用面向过程的思路来理解，两个依次 一听就是两个循环，我们来实现
function insertionSort( _array ){
//取出第一个元素，并当做有序数组
var _sortArray = [ _array.shift() ];
//依次拿待排序的数组元素和有序作比较，那么他的循环结束条件就是待排序数组都比较完了
while( _array.length ){
//取出待排序数组的第一个元素
var _first = _array.shift();
//依次和有序数组从后往前的元素作比较，那么第一个数的索引就是
var _i = _sortArray.length - 1; //这里_sortArray[i]就是最后一个元素了
}
}
4、下一步呢我们就要依次循环去比较了，这里要弄清楚循环结束的条件，应该是当找到和当前比较的元素更大/小的时，或者所有元素都比较完毕时（此时肯定他就是最小的了) 。
所以我们继续实现
function insertionSort( _array ){
//取出第一个元素，并当做有序数组
var _sortArray = [ _array.shift() ];
//依次拿待排序的数组元素和有序作比较，那么他的循环结束条件就是待排序数组都比较完了
while( _array.length ){
//取出待排序数组的第一个元素
var _first = _array.shift();
//依次和有序数组从后往前的元素作比较，那么第一个数的索引就是
var _i = _sortArray.length - 1; //这里_sortArray[i]就是最后一个元素了
//当索引大于等于0 就是还没有比较结束 而且 当前元素 仍然小于 比较元素时，循环继续，否则找到位置，循环退出
while( _i >= 0 && _first < _sortArray[_i]){
//既然进入循环了，就说明满足条件，那么当前的数就往后移一位
_sortArray[ _i + 1 ] = _sortArray[_i];
//同时比较的索引也要左移一位
_i--;
}
//里面的小循环结束后，当前的i + 1的位置 就是元素要插入的位置
_sortArray[ _i + 1 ] = _first;
}
return _sortArray;
}
ok
插入排序实现完毕，这些基础的排序思想还是很容易理解的，多看几遍相信大家就懂了
引申
老规矩，系列完毕后，在进行优化相关的知识讨论
狗的拜！
网友评论