成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Javascript算法——希爾排序

lowett / 2007人閱讀

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

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

一圖勝千言：

1. 算法介紹 1.1 算法描述

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

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

但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；

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

1.2 算法步驟

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

按增量序列個(gè)數(shù) k，對序列進(jìn)行 k 趟排序；

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

1.3 算法實(shí)現(xiàn) 
function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動(dòng)態(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;
}

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

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

相關(guān)文章

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

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

    haitiancoder 評論0 收藏0

  • javascript數(shù)據(jù)結(jié)構(gòu)與算法 --- 高級排序算法

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

    qianfeng 評論0 收藏0

  • 算法筆記(JavaScript版)——排序

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

    ctriptech 評論0 收藏0

  • JavaScript 版各大排序算法

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

    FrozenMap 評論0 收藏0

  • 算法：排序算法總結(jié)（JavaScript描述）

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

    dkzwm 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<