基于JavaScript實現的希爾排序算法分析
更新時間：2017年04月14日 10:23:49 作者：布瑞澤的童話
這篇文章主要介紹了基于JavaScript實現的希爾排序算法,簡單分析了希爾排序的原理并結合實例形式給出了javascript實現希爾排序的操作步驟與相關注意事項,需要的朋友可以參考下
本文實例講述了基于JavaScript實現的希爾排序算法。分享給大家供大家參考，具體如下：
通過對直接插入排序的分析，可知其時間復雜度為O（n2），但是，如果待排序序列為正序時，其時間復雜度可提高至O（n）。希爾排序正是對此進行改進的排序。希爾排序的核心理念與插入排序不同，它會首先比較距離較遠的元素，而非相鄰元素。通過定義一個間隔序列來表示在排序過程中進行比較的元素之間有多遠的間隔。
下圖演示了希爾排序中間隔序列是如何運行的：
下面我們通過js來實現希爾排序，代碼如下：
<!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){//顯示數組
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>
其排序過程如下：
希爾排序根據間隔序列的選取不同，時間復雜度也不同，但是需要注意，應該使間隔序列中的值沒有除1以外的公因子，并且最后一個間隔值必須等于1。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
相關文章
最新發(fā)布的CKFinder 1.4版 已經提供了對CKEditor3.0的支持2010-01-01
這篇文章主要分享了一則javascript 調試技巧,需要的朋友可以參考下2015-01-01
JSON 在很多場合下作為數據格式比XML要更加方便。JSON的數據由對象、數組和元素等格式組成。每種格式都可以包含合法的JavaScript數據類型2014-01-01
JavaScript對象的創(chuàng)建模式與繼承模式示例講解
繼承機制是面向對象程序設計使代碼可以復用的最重要的手段，它允許程序員在保持原有的特性基礎上進行擴展，增加功能，這樣產生新的類，稱作是派生類。繼承呈現了面向對象程序設計的層析結構，體現了由簡單到復雜的認知過程。繼承是類設計層次的復用2022-12-12
電商系統(tǒng)中訂單、庫存中有數字等加減乘除算術,下面這篇文章主要給大家介紹了關于利用Math.js解決JS計算小數精度丟失問題的相關資料,mathjs是一個前端在計算上面必定會用到的類庫,需要的朋友可以參考下2022-04-04
這篇文章主要介紹了JavaScript監(jiān)聽觸摸事件代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了微信小程序uploadFile接口實現文件上傳流程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
這篇文章主要介紹了前端中跨域及解決措施的相關資料,主要方法包括JSONP、CORS和服務器代理跨域,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2025-02-02
ES6中的迭代器、Generator函數及Generator函數的異步操作方法
這篇文章主要介紹了ES6中的迭代器、Generator函數以及Generator函數的異步操作方法，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2019-05-05
這篇文章主要介紹了JavaScript 如何計算文本的行數的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09