Javascript实现直接插入排序算法

热网热热 5评论
插入排序也是计算机科学中的基本的、简单的、经典的排序算法,之前文章我们已经介绍了通过JavaScript实现冒泡排序、通过JavaScript实现快速排序。今天分享一下我对直接插入排序的理解,以及通过JavaScript来实现。

插入排序算法思想

插入排序就是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
插入排序算法其实还是比较简单的,分为直接插入排序和希尔排序。

直接插入算法

假设待排序的记录存放在数组R[1..n]中,初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。
这种概念看着有点让人摸不清头脑,对于一个待排序序列,我们不知道哪儿是有序序列,哪儿是无序的。其实这里就需要我们自己去创造一个有序序列,从0开始。
直接插入排序算法
比如有一个待排序数组,我们默认第一项就是一个有序序列,我们从第二项开始,比较第一项与第二项值的大小,来确定往第一项(有序序列)插入的位置,接下来第三项根据大小插入到有序序列,如此反复直到最后一项插入到数组有序序列中。

JavaScript实现直接插入排序

function InsertSort(R){
var Sentinel;
for(var i = 1; i < R.length; i++){
if(R[i] < R[i - 1]){
Sentinel = R[i]
for(var n =  i - 1; Sentinel < R[n]; n--){
R[n+1] = R[n]
}
R[n+1] = Sentinel;
}
}
return R;
}
var a = [6,3,4,5,8,1,5,9,11,0,7,2]
var m = InsertSort(a)
console.log(JSON.stringify(m))//[0,1,2,3,4,5,5,6,7,8,9,11]
最外层for循环是从无序区取值,然后保存所取得的值,里层循环是寻找插入位置,有个很关键的地方在于for循环条件控制选择的是Sentinel < R[n],满足这一条件n+1的位置就是该插入的位置,这里也是一个技巧。

算法的时间性能分析

对于具有n个记录的文件,要进行n-1趟排序。
各种状态下的时间复杂度:
算法的空间复杂度分析
算法所需的辅助空间是一个监视哨,辅助空间复杂度O(1)。是一个就地排序。
直接插入排序是稳定的排序方法,排序过程中不会改变大小相等元素的相对位置。
 

转载请注明觅施南网,Javascript实现直接插入排序算法:https://www.rewonng.com/qianduanzhishi/152.html

查看剩余内容

相关内容推荐

猜你喜欢内容