算法-基數排序

cucumber 發布于2019-08-22 16:25 / 1148人閱讀

摘要：步驟一以下個位排序，得到。號桶號桶號桶號桶號桶號桶號桶號桶號桶號桶基數排序生成隨機數保留整數清空數據插入數據裝換為字符串交換位置從低位開始進行排序元素的最高位數第一輪，取個位第二輪，去十位從頭開始取個人博客鏈接

算法思想

1.定義:基數排序按照對位數分組的順序的不同，LSD（從低位開始）和MSD（從高位開始）基數排序.

2.算法思路（LSD）：

第一：定義長度十位數組(桶)，存放排好序的數組；

第二：個位排序，個位大小對應桶編號，然后取出；

第三：十位排序，十位大小對應桶編號，然后取出；

第四：百位排序，百位大小對應桶編號，然后取出，0-1000的排序完成；

3.例子：比較3 0 6 12 12 7 8 12 13 12 8 11 12 4。

步驟一：以下個位排序，得到0 11 12 12 12 12 12 3 13 4 6 7 8 8。

0號桶 [ 0 ]
1號桶 [ 11 ]
2號桶 [ 12, 12, 12, 12, 12 ]
3號桶 [ 3, 13 ]
4號桶 [ 4 ]
5號桶 [ ]
6號桶 [ 6 ]
7號桶 [ 7 ]
8號桶 [ 8, 8 ]
9號桶 [ ]

步驟二：將以上個位排序好的，然后進行十位排序，得到0 3 4 6 7 8 8 11 12 12 12 12 12 13。

0號桶 [ 0, 3, 4, 6, 7, 8, 8 ]
1號桶 [ 11, 12, 12, 12, 12, 12, 13 ]
2號桶 [ ]
3號桶 [ ]
4號桶 [ ]
5號桶 [ ]
6號桶 [ ]
7號桶 [ ]
8號桶 [ ]
9號桶 [ ]

/*
 * @Author: yt.gan 
 * @Date: 2018-04-17 09:53:22 
 * @Last Modified by: yt.gan
 * @Last Modified time: 2018-04-17 10:57:14
 */

//基數排序
function CArray(elements) {
    this.dataStore = [];
    this.pos = 0;
    this.elements = elements;
    for (var i = 0; i < this.elements; ++i) {
        this.dataStore[i] = i;
    }
    this.setData = function() {
        //生成隨機數
        //floor保留整數 random [0,1)
        for (var i = 0; i < this.elements; ++i) {
            this.dataStore[i] = Math.floor(Math.random() * (this.elements + 1));
        }
    }

    this.clear = function() {
        //清空數據
        for (var i = 0; i < this.dataStore.length; ++i) {
            this.dataStore[i] = 0;
        }
    }

    this.insert = function(element) {
        //插入數據
        this.dataStore[this.pos++] = element;
    }

    this.show = function() {
        //裝換為字符串
        var reStr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
            reStr += this.dataStore[i] + " ";
            if (i > 0 & i % 10 == 0) {
                reStr += "
";
            }
        }
        console.log(reStr);
    }

    this.swap = function(arr, index1, index2) {
        //交換位置
        var temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    this.radix = function(arr, maxBit) {
        //LSD 從低位開始進行排序
        //maxBit 元素的最高位數
        var mod = 10;
        var dev = 1;
        var temp = [];
        for (var i = 0; i < maxBit; i++, dev *= 10, mod *= 10) {
            //第一輪mod=10，dev=1 取個位
            //第二輪mod=100，dev=10 去十位
            for (var j = 0; j < arr.length; j++) {
                var bucket = parseInt((arr[j] % mod) / dev);
                if (temp[bucket] == null) {
                    temp[bucket] = [];
                }
                temp[bucket].push(arr[j]);
            }
            console.log(temp);
            var pos = 0;
            for (var j = 0; j < temp.length; j++) {
                var value = null;
                if (temp[j] != null) {
                    //從頭開始取
                    while ((value = temp[j].shift()) != null) {
                        arr[pos++] = value;
                    }
                }
            }
        }
    }
}

var myNums = new CArray(14);
myNums.setData();
myNums.show();
myNums.radix(myNums.dataStore, 2);
myNums.show();

// 3 0 6 12 12 7 8 12 13 12 8 11 12 4

// [ [ 0 ],
//   [ 11 ],
//   [ 12, 12, 12, 12, 12 ],
//   [ 3, 13 ],
//   [ 4 ],
//   ,
//   [ 6 ],
//   [ 7 ],
//   [ 8, 8 ] ]

// [ [ 0, 3, 4, 6, 7, 8, 8 ],
//   [ 11, 12, 12, 12, 12, 12, 13 ],
//   [],
//   [],
//   [],
//   ,
//   [],
//   [],
//   [] ]

// 0 3 4 6 7 8 8 11 12 12 12 12 12 13

個人博客鏈接

GPU云服務器云服務器基數排序 opencl基數排序基數排序當數據量很大的時候代碼最大基數匹配算法

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

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

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

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

Awbeci 2019-08-26 10:24 評論0 收藏0
前端排序算法總結

摘要：前言排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎當然，排序和查找兩類算法是面試的熱門選項。本篇將會總結一下，在前端的一些排序算法。函數的性能相信對于排序算法性能來說，時間復雜度是至關重要的一個參考因素。前言排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較你和一個連快排都不會寫的人的時...

happen 2019-08-21 16:40 評論0 收藏0
計數排序，桶排序與基數排序

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

GitChat 2019-08-22 13:56 評論0 收藏0
排序算法 JavaScript

摘要：一冒泡排序算法介紹比較相鄰的兩個元素如果前一個比后一個大，則交換位置。它與冒泡排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序的核心在于間隔序列的設定。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。一、冒泡排序算法介紹：比較相鄰的兩個元素,如果前一個比后一個大，則交換位置。第一輪把最大的元素放到了最后面。由于每次排序最后一個都是最大的，...

Charlie_Jade 2019-08-23 15:18 評論0 收藏0
快速排序js實現

摘要：然后再分別對基數左邊和右邊的數組進行相同的操作，直到數組中只有一個元素時，返回該數組。快速排序算法今天大概講下使用js實現快速排序算法：快速排序算法的思想類似于二分法，每次都是在數組中選擇一個基數（可以是任意一個位置的數，不過一般選擇中間的數字或者最左邊的數字），每一輪結束后，比該基數小的數都位于該基數的左邊，比該基數大的數都位于該基數的右邊。然后再分別對基數左邊和右邊的數組進行...

zhoutk 2019-08-22 16:22 評論0 收藏0