展示型网站多少钱,wordpress图片cdn,2021最旺公司名字,做个淘宝客网站怎么做插入排序是什么
插入排序#xff08;Insertion Sort#xff09;#xff0c;一般也被称为直接插入排序。对于少量元素的排序#xff0c;它是一个有效、简单的算法
其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中#xff0c;最终得到的序列就是已经排…插入排序是什么
插入排序Insertion Sort一般也被称为直接插入排序。对于少量元素的排序它是一个有效、简单的算法
其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中最终得到的序列就是已经排序好的数据
插入排序的工作方式像许多人排序一手扑克牌开始时我们的左手为空并且桌子上的牌面向下
然后我们每次从桌子上拿走一张牌并将它插入左手中正确的位置该正确位置需要从右到左将它与已在手中的每张牌进行比较 看下图 这个就非常形象的展示了什么是插入排序
用代码实现插入排序如下
// 插入排序
function insertionSort(arr) {const len arr.length;let preIndex, current;for (let i 1; i len; i) {preIndex i - 1;current arr[i];while(preIndex 0 arr[preIndex] current) {arr[preIndex1] arr[preIndex];preIndex--;}arr[preIndex1] current;}return arr;
}在插入排序中当待排序数组是有序时是最优的情况只需当前数跟前一个数比较一下就可以了这时一共需要比较N- 1次时间复杂度为O(n)
最坏的情况是待排序数组是逆序的此时需要比较次数最多总次数记为123…N-1所以插入排序最坏情况下的时间复杂度为O(n^2)
通过上面了解可以看到插入排序是一种稳定的排序方式
应用场景
插入排序时间复杂度是 O(n2)适用于数据量不大算法稳定性要求高且数据局部或整体有序的数列排序
参考链接 https://vue3js.cn/interview/algorithm/insertionSort.html#%E4%BA%8C%E3%80%81%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0
