Javascript排序算法之計數排序的實例

2019-11-20 20:51:43

字體：大中小

來源：轉載

供稿：網友

計數排序(Counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組Count_arr，其中第i個元素是待排序數組Arr中值等于i的元素的個數。然后根據數組Count_arr來將Arr中的元素排到正確的位置。
分為四個步驟：
1.找出待排序的數組中最大和最小的元素
2.統計數組中每個值為i的元素出現的次數，存入數組Count_arr的第i項
3.對所有的計數累加（從Count_arr中的第一個元素開始，每一項和前一項相加）
4.反向遍歷原數組：將每個元素i放在新數組的第Count_arr(i)項，每放一個元素就將Count_arr(i)減去1

實例：

復制代碼代碼如下:

/**
 * 計數排序是一個非基于比較的排序算法，
 * 該算法于1954年由 Harold H. Seward 提出。
 * 它的優勢在于在對一定范圍內的整數排序時，
 * 它的復雜度為Ο(n+k)（其中k是整數的范圍），
 * 快于任何比較排序算法。
 *
 */

function countSort(arr, min, max) {
    var i, z = 0, count = [];

    for (i = min; i <= max; i++) {
        count[i] = 0;
    }

    for (i=0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    for (i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
        }
    }
    return arr;
}

// test

var i, arr = [];

for (i = 0; i < 100; i++) {
    arr.push(Math.floor(Math.random() * (141)));
}

countSort(arr, 0, 140);