本文實例講述了基于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];//定義間隔區間 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程序設計有所幫助。
新聞熱點
疑難解答
