快捷導(dǎo)航

基于JavaScript實(shí)現(xiàn)的希爾排序算法分析

更新時間：2017年04月14日 10:23:49 作者：布瑞澤的童話

這篇文章主要介紹了基于JavaScript實(shí)現(xiàn)的希爾排序算法,簡單分析了希爾排序的原理并結(jié)合實(shí)例形式給出了javascript實(shí)現(xiàn)希爾排序的操作步驟與相關(guān)注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了基于JavaScript實(shí)現(xiàn)的希爾排序算法。分享給大家供大家參考，具體如下：

通過對直接插入排序的分析，可知其時間復(fù)雜度為O（n2），但是，如果待排序序列為正序時，其時間復(fù)雜度可提高至O（n）。希爾排序正是對此進(jìn)行改進(jìn)的排序。希爾排序的核心理念與插入排序不同，它會首先比較距離較遠(yuǎn)的元素，而非相鄰元素。通過定義一個間隔序列來表示在排序過程中進(jìn)行比較的元素之間有多遠(yuǎn)的間隔。

下圖演示了希爾排序中間隔序列是如何運(yùn)行的：

下面我們通過js來實(shí)現(xiàn)希爾排序，代碼如下：

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript希爾排序</title>
</head>
<body>
<script type="text/javascript">
  function shellSort(nums){//希爾排序
    var gaps=[5,3,1];//定義間隔區(qū)間
    for(var g=0;g<gaps.length;g++){//一個一個間隔值開始
      for(var i=gaps[g];i<nums.length;i++){//以間隔值遍歷
        var temp=nums[i];//選中元素
        for(var j=i;j>=gaps[g]&&nums[j-gaps[g]]>temp;j-=gaps[g]){//如果前面一個大于后面一個
          nums[j]=nums[j-gaps[g]];//后移
        }
        nums[j]=temp;//填補(bǔ)
      }
    }
  }
  function show(nums){//顯示數(shù)組
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+' ');
    }
    document.write('<br>');
  }
  var nums=[6,0,2,9,3,5,8,0,5,4];
  show(nums);//6 0 2 9 3 5 8 0 5 4
  shellSort(nums);//希爾排序
  show(nums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

其排序過程如下：