国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

Javascript算法——希爾排序

lowett / 2000人閱讀

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

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

一圖勝千言：

1. 算法介紹 1.1 算法描述

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

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

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

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

1.2 算法步驟

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

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

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

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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/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 評(píng)論0 收藏0

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

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

    qianfeng 評(píng)論0 收藏0

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

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

    ctriptech 評(píng)論0 收藏0

  • JavaScript 版各大排序算法

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

    FrozenMap 評(píng)論0 收藏0

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

    摘要：二代碼簡(jiǎn)單選擇排序一分析循環(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)定 簡(jiǎn)單選擇排序 O(n^2) O(n^2)...

    dkzwm 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

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