用JS寫計數排序、基數排序

tulayang 發布于2019-08-20 19:10 / 1150人閱讀

摘要：計數排序計數排序就是簡單的桶排序，一個桶代表數組中一個數出現的個數，所以需要一個和數組數字范圍一樣大的輔助數組，一般用在范圍小于的排序，時間復雜度為，空間復雜度為數組的數字范圍。

計數排序

計數排序就是簡單的桶排序，一個桶代表數組中一個數出現的個數，所以需要一個和數組數字范圍一樣大的輔助數組，一般用在范圍小于100的排序，時間復雜度為O(n)，空間復雜度為數組的數字范圍。

/**
 * 范圍在 start - end 之間的排序
 * 計數排序需要輔助數組，該輔助數組的長度是待排序數組的范圍，所以一般用作范圍小于100的排序
 */
function countSort(arr, start, end) {
    var len = arr.length;
    // 桶數組
    var suportArr = new Array(end - start + 1);
    // 結果數組
    var resArr = new Array(len);
    // 初始化桶數組
    for (i = 0; i < suportArr.length; i++) {
        suportArr[i] = 0;
    }
    // 待排序數組中的數組出現，在桶子對應位置+1代表這個數出現的個數+1了
    for (let i = 0; i < len; i++) {
        suportArr[arr[i]]++;
    }
     // 從第1項開始，桶數組加上前一個桶的個數，現在輔助數組的意義變成了每一項的排名了。
    for (let i = 1; i < suportArr.length; i++) {
        suportArr[i] += suportArr[i - 1];
    }
    // 根據輔助數組的排名，從后往前賦值
    for (let i = len - 1; i >= 0; i--) {
        resArr[suportArr[arr[i]] - 1] = arr[i];
        suportArr[arr[i]]--;
    }

    return resArr;
}

基數排序

基數排序是多躺的桶排序

var radix = 16; // 基數，可以為任何數，越大趟數越小，但是桶數越多，最好根據最大數字進行定義。
function _roundSort(arr, round, radix) {
    var buckets = new Array(radix);

    for (let i = 0; i < radix; i++) {
        buckets[i] = [];
    }
    // 將數組中的數放進對應的桶子中
    for (let i = 0; i < arr.length; i++) {
        let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;

        buckets[remainder].push(arr[i]);
    }

    // 將數組重新根據桶子進行排序
    var index = 0;
    for (let i = 0; i < buckets.length; i++) {
        for (let j = 0; j < buckets[i].length; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

function radixSort(arr, round) {
    for (let i = 1; i <= round; i++) {
        _roundSort(arr, i, radix);
    }
    return arr;
}

console.log(radixSort([10,5,5,50,0,155,4622,5,1,4,2154], 4));

云服務器 GPU云服務器基數排序 opencl基數排序計數排序基數排序當數據量很大的時候代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/85238.html

JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者...

Awbeci 2019-08-26 10:24 評論0 收藏0
計數排序，桶排序與基數排序

摘要：涉及的算法有計數排序基數排序桶排序，它們被歸類為非比較排序。計數排序沒有對元素進行比較，只是利用了箱與元素的一一對應關系，根據箱已經排好序的先決條件，解決排序。基數排序，是按照從高位到低位的順序進行分組排序。內部排序也是用基數排序。一般算法能做到O(logn)，已經非常不錯，如果我們排序的對象是純數字，還可以做到驚人的O(n)。涉及的算法有計數排序、基數排序、桶排序，它們被歸類為非比...

GitChat 2019-08-22 13:56 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
數據結構以及相關排序

摘要：桶排序與計數排序的區別桶排序中一個桶可以放一個范圍內的多個數據，在各個桶中又可以用其他方法排序，其快速之處在于只用對比同一個桶內的數字而無需與其他桶的數字作對比。與計數排序相比，桶排序需要作二次對比，但可省略桶的個數。哈希表（Hash Table）所有符合鍵值對即key-value的結構就是哈希。數組其實也是一種哈希。計數排序（復雜度(n+max)）無法統計負數和小數，需要一個...

Brenner 2019-08-23 12:20 評論0 收藏0
前端面試必備——十大經典排序算法

摘要：冒泡排序冒泡排序也是一種簡單直觀的排序算法。但希爾排序是非穩定排序算法。快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。冒泡排序冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就...

RebeccaZhong 2019-08-20 18:24 評論0 收藏0