Javascript算法——希爾排序

lowett 發(fā)布于2019-08-20 16:38 / 2046人閱讀

摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。這里主要介紹希爾排序。一圖勝千言算法介紹算法描述希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。

常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。這里主要介紹希爾排序。

一圖勝千言：

1. 算法介紹 1.1 算法描述

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；

但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行依次直接插入排序。

1.2 算法步驟

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個數(shù) k，對序列進行 k 趟排序；

每趟排序，根據(jù)對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

1.3 算法實現(xiàn)

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動態(tài)定義間隔序列
        gap = gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

GPU云服務器云服務器希爾排序排序算法圖解排序算法總結桶排序算法

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/83058.html

JavaScript 數(shù)據(jù)結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
javascript數(shù)據(jù)結構與算法 --- 高級排序算法

摘要：高級排序算法總結希爾排序間隔序列可以動態(tài)定義，不過對于大部分的實際應用場景，算法要用到的間隔序列可以提前定義好有一些公開定義的間隔序列，使用它們會得到不同的結果。高級排序算法總結希爾排序 function shellsort(array, gaps) { for (var g = 0; g < gaps.length; g++) { for ...

qianfeng 2019-08-26 11:34 評論0 收藏0
算法筆記(JavaScript版)——排序

摘要：算法筆記版排序本文內(nèi)容根據(jù)和的算法第四版整理，原代碼為語言，自己修改為版本，僅供參考。希爾排序的思想是使數(shù)組中任意間隔為的元素都是有序的。使用遞增序列，，，，，的希爾排序所需的比較次數(shù)不會超過的若干倍乘以遞增序列的長度。算法筆記(JavaScript版)——排序本文內(nèi)容根據(jù)Rebert Sedgewick和Kevin Wayne的《算法（第四版）》整理，原代碼為java語言，自己修...

ctriptech 2019-08-22 10:34 評論0 收藏0
JavaScript 版各大排序算法

摘要：推薦一下，，這里還有個可視化的排序博客，各大排序算法的實現(xiàn)都栩栩如生。堆排序堆排序是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。共勉參考維基百科排序搜索聊一聊排序算法秒殺種排序算法版排序圖解排序算法實現(xiàn)歡迎來我的博客交流最近看到了很多公司都在準備明年的實習校招，雖然離三月份還有一段時間，感覺已經(jīng)可以準備了。在網(wǎng)上看了一些排序算法和數(shù)組去重操作，感覺都寫的很好，心血來潮，也來寫一寫。 s...

FrozenMap 2019-08-20 13:47 評論0 收藏0
算法：排序算法總結（JavaScript描述）

摘要：二代碼簡單選擇排序一分析循環(huán)次，每一次的當前項與其之后的項作比較，找出其中最小的那個，與當前項交換。二代碼希爾排序是一種改進版的插入排序，縮小增量排序。這樣做的目的是因為，直接插入排序在序列基本有序時效率最高。排序算法平均情況最好情況最壞情況輔助空間穩(wěn)定性冒泡排序 O(n^2) O(n) O(n^2) O(1) 穩(wěn)定簡單選擇排序 O(n^2) O(n^2)...

dkzwm 2019-08-23 11:45 評論0 收藏0