首页 > 代码库 > 直接插入排序算法(Javascript版本)

直接插入排序算法(Javascript版本)

将n个元素的数列分为已有序和无序两个部分。

数列:{a1,a2,a3,a4,…,an}

将该数列的第一元素视为有序数列,后面都视为无序数列:

{{a1},{a2,a3,a4,…,an}}

将无序数列中的元素插入到有序数列的对应位置,插入前通过比大小的方式找到其在有序数列中的对应位置。

 

代码:

以下代码在nodejs环境中执行通过。

function sort(elements){  //假设第0个元素是一个有序的数列,第1个以后的是无序的序列,  //所以从第1个元素开始将无序数列的元素插入到有序数列中  for(var i = 1; i < elements.length; i++){    //升序    if(elements[i] < elements[i-1]){      //取出无序数列中的第i个作为被插入元素      var guard = elements[i];      //记住有序数列的最后一个位置,并且将有序数列位置扩大一个      var j = i - 1;      elements[i] = elements[j];            //比大小,找到被插入元素所在的位置      while(j >= 0 && guard < elements[j]){        elements[j+1] = elements[j];        j--;      }      //插入      elements[j+1] = guard;    }  }}var elements = [10, 9, 8, 7, 6, 5];console.log(‘before: ‘ + elements);sort(elements);console.log(‘ after: ‘ + elements);

 

效率:

最好:n

最坏:O(n^2)

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

直接插入排序算法(Javascript版本)