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

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

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

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

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

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

下面我們通過js來實現(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;//填補
      }
    }
  }
  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>

其排序過程如下：