[JS排序算法] - 3 - 插入排序
文章目录
插入排序(英语:Insertion Sort)是一种简单直观的[排序算法]。
它的工作原理是通过构建有序序列,对于未排序数据,
在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),
因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,
为最新元素提供插入空间。
解释
以上是 维基百科 关于插入排序的描述。其实插入排序的核心点就在于:
- 如何往一个
有序数组中添加一个新元素,使之插入后的新数组仍保持有序状态
有序数组中添加元素后 数组仍保持有序状态
/**
* @param{有序数组}arr
* @param{要插入的值}val
*/
function insert(old_arr, new_val){
// 获取到数组中最后一个元素
// 因为原数组是有序数组 所以该元素确定是数组中最大值
let p = old_arr.length - 1;
// 新元素和最后一个元素进行比较
while(new_val < arr[p]){
// 新元素比数组中最大的元素还大, 需要在中间进行插入
// 预留位置
arr[p+1] = arr[p]
// 由后往前继续while判断
p--;
}
// 把新元素放到合适的位置
// 上方的while循环可能走了 也可能没走
// 如果新元素大于原数组中的最后一个值 直接放到最后就好
// 如果新元素小于原数组中的最后一个值 才会走while循环
arr[p+1] = new_val;
}
测试一下
const _arr= [1, 3, 5, 6, 7, 9, 12, 13, 14, 16, 25];
insert(_arr, 15);
console.log(_arr);
// [ 1, 3, 5, 6, 7, 9, 12, 13, 14, 15, 16, 25]
实现了往一个有序数组中添加一个元素后 数组仍保持有序状态后,再去实现插入排序就十分简单了。
其实道理是一样的,只不过把插入逻辑推广到无序数组中:
JS实现插入排序
/**
* @param{无序数组}arr
*/
function insert_sort(arr){
// 从下标1开始 循环遍历无序数组
for(let i = 1; i < arr.length; i++){
// 假设数组前i项都是有序状态
// 并且将p指向有序数组中的最后一个元素
let p = i - 1;
// 那么此时新元素就是有序数组中最后一个元素的下一个元素
const new_val = arr[p+1];
// 眼熟的 while 循环
while(new_val < arr[p]){
arr[p+1] = arr[p];
p--;
}
arr[p+1] = new_val
}
}
测试一下
const _arr = [5, 8, 1, 3, 2, 4, 9, 0.5];
insert_sort(_arr);
console.log(_arr);
// [ 0.5, 1, 2, 3, 4, 5, 8, 9 ]
其实插入排序就是去遍历数组,第一次先默认前1项是已排好序的状态(数组中只有一项的话本身就可以理解为是排好序的状态)。 接着去判断第二个,第三个...
如果其中某个元素大于了有序数组的最后一项,不用做处理;如果其中某个元素小于了有序数组的最后一项,也就是小于了有序数组的最大值。那么此时就需要做插入,插入的时候注意要保留预留位置,就是让上一个元素等于该元素本身。依次由后往前做判断,找到合适位置之后将新元素插入到该位置即可。由此可见,插入排序的时间复杂度为O(n^2),空间复杂度因为多了一个预留位置,所以是O(1)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论