用JS写计数排序、基数排序

tulayang 发布于2019-08-20 19:10 / 1149人阅读

摘要：计数排序计数排序就是简单的桶排序，一个桶代表数组中一个数出现的个数，所以需要一个和数组数字范围一样大的辅助数组，一般用在范围小于的排序，时间复杂度为，空间复杂度为数组的数字范围。

计数排序

计数排序就是简单的桶排序，一个桶代表数组中一个数出现的个数，所以需要一个和数组数字范围一样大的辅助数组，一般用在范围小于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基数排序计数排序基数排序当数据量很大的时候代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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