DIV CSS 佈局教程網

JavaScript 排序演算法:希爾排序實戰兩例
編輯:JavaScript基礎知識     

插入排序在處理近乎已排序的資料時效率極高,可達到線性排序的水準;但它一般偏低效,因為每次只能把資料移動一個位置。希爾排序(Shell sort)正是針對這兩點提出的改良版本。

這個演算法以其設計者希爾(Donald Shell)命名,於 1959 年發表。部分舊版教科書稱之為 Shell-Metzner,但據 Metzner 本人說法,他並未參與其中,名字不應被冠上。

基本思想:先取一個小於 n 的整數 d1 作為第一個增量,把全部記錄分成 d1 組,將距離為 d1 倍數的記錄歸在同一組,先在各組內做直接插入排序;接著取第二個增量 d2 < d1 重複分組與排序,直到增量 dt=1,此時所有記錄歸在同一組做插入排序為止。本質上,它是一種分組插入的方法。

實例一:

function shellSort(list) {
    var gap = Math.floor(list.length / 2);

    while (gap > 0) {
        for (i = gap; i < list.length; i++) {
            temp = list[i];

            for (j = i; j >= gap && list[j - gap] > temp; j -= gap) {
                list[j] = list[j - gap];
            }
            list[j] = temp;
        }
        gap = Math.floor(gap / 2);
    }

    return list;
};

// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
shellSort(arr);

實例二:

<script type="text/javascript">
function shellSort(array) {
    var j, i, v, h = 1, s = 3, k, n = array.length;
    var result = "";
    var count = 0;
    while (h < n)
        h = s * h + 1;

    while (h > 1) {
        h = (h - 1) / s;
        for (k = 0; k < h; k++)
            for (i = k + h, j = i; i < n; i += h, j = i) {
                v = array[i];
                while (true)
                    if ((j -= h) >= 0 && array[j] > v)
                        array[j + h] = array[j];
                    else
                        break;
                array[j + h] = v;
            }
        count++;
        result += "<br />第" + count + "遍排序的結果是:";
        for (var n = 0; n < array.length; n++) {
            result += array[n] + ",";
        }
    }
    return result;
}
</script>
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved