JS--排序演算法之計數和基數排序

来源:https://www.cnblogs.com/luoshuifushen/archive/2020/03/22/12544447.html

JS 排序演算法之計數和基數排序 [Toc] 計數排序 利用數組的index是天然有序的特征來排序. 例如: 已知一個亂序數組的範圍是0~10,長度未知, 我們只需要遍歷一遍數組,點出每個值出現的次數,並用一個新數組來存儲這個次數,就能做到排序. 假如數字1出現3次, 那麼新數組newAry[1]=3 ...


JS-排序演算法之計數和基數排序

計數排序

利用數組的index是天然有序的特征來排序. 例如: 已知一個亂序數組的範圍是0~10,長度未知, 我們只需要遍歷一遍數組,點出每個值出現的次數,並用一個新數組來存儲這個次數,就能做到排序. 假如數字1出現3次, 那麼新數組newAry[1]=3, 在新數組遍歷的時候輸出3次"1"

  • 時間複雜度O(n~K)
  • 穩定的排序演算法
  • 性能: 由於是非比較排序, 速度快於其他任何排序演算法,
  • 缺點: 需要知道數組值的範圍, 且不適用於範圍波動很大但長度小的數組
    • 例如: 數組長度10, 但是值的範圍在 0~1000000, 計數排序用來計數的數組將會很大
  • 特點: 先遍曆數組計算數值出現次數, 然後就排序好了...
    function countSort(ary) {
        let newAry = new Array(ary.length).fill(0);
        for (const value of ary) {
            newAry[value]++;
        }
        ary = [];
        // 給ary重新賦值
        for(var i =0; i<newAry.length; i++) {
            // 迴圈數字次數
            for(var k = newAry[i]; k>0; k--) {
                ary.push(i);
            }
        }
        newAry = null;
        return ary;
    }

效果演示:

計數排序.gif

基數排序

從左到右按位排序, 先排個位, 再排十位,百位... 需要用到計數排序的方法-使用數組計數

    function radixSort(ary) {
    // 獲取最大值
    let maxNum = Math.max.apply(Math, ary);
    let t = 1,
        bucketAry = new Array(10), // 0~9的數組,用來計算數字出現次數
        temp = new Array(ary.length); // 交換數組, 用來臨時存儲排序的數
    // 這一步是計算最大數有多少位,這個位數就是要迴圈的次數
    while ((maxNum /= 10) >= 1) {
        t++;
    }
    let rate = 1,
        K= null;
    for (let i = 1; i <= t; i++) {
        // 計數數組歸零
        bucketAry.fill(0);
        // 清點數字次數
        ary.forEach((item) => {
            // 求數字最後一位的值
            k = Math.floor(item / rate) % 10;
            bucketAry[k]++;
        });
        // 通過數字次數得到該數字應該在數組中的位置
        bucketAry.reduce((total, item, index) => {
            bucketAry[index] = total + item;
            return total + item
        });
        // 通過計算的順序將ary中數存入temp數組中
        for (let j = ary.length - 1; j >= 0; j--) {
            k = Math.floor(ary[j] / rate) % 10;
            temp[bucketAry[k] - 1] = ary[j];
            bucketAry[k]--;
        }
        // 將temp相同位置的值負值給ary, 不能直接 ary = temp
        ary = ary.map((item, index)=>temp[index]);
        rate *= 10;
    }
    temp = null;
    bucketAry = null;
    return ary;
}

效果演示:

基數排序.gif


您的分享是我們最大的動力!

更多相關文章
  • 在網頁上找了半天,發現現在的資源實在是少的可憐,而前端尤甚。所以沒辦法,於是自己花了一些時間寫了一個; 1 /** 2 * 刪除URL中的指定參數 3 * @param {*} url 4 * @param {*} name 5 */ 6 function delUrlParams(url, nam ...
  • 今天學習node的時候連接mysql報了這麼一個錯誤: MySQL 8.0 Client does not support authentication protocol requested by server; consider upgrading MySQL client, 這麼一長條我也看不懂 ...
  • 作者:Filip Rakowski 翻譯:啟道學院 我們已經知道,在Vue的新版本中編寫的應用程式將表現得非常好,但性能並不是最重要的部分。 對我們開發人員來說最重要的是新版本將如何影響我們編寫代碼的方式。 正如你所預料的,Vue3帶來了許多新的振奮人心的功能。 幸運的是,Vue團隊主要對當前的Co ...
  • "最新博客鏈接" "Github鏈接" 查看此文檔前應先瞭解, "vuepress基本操作" 參考官方文檔進行配置: "vuepress theme reco" "VuePress" "SamKirkland / FTP Deploy Action" 最終效果 "最終效果鏈接" 思路 下載vuepr ...
  • 訂單頁效果圖: 目錄結構 order.html <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>order</title> <meta name="viewport" content="width=devic ...
  • [TOC] "最新博客鏈接" "VuePress 線上文檔鏈接_Github Pages" "VuePress 線上文檔鏈接_博客伺服器" (如果上面進不去,可以進這個,伺服器在阿裡雲) "Github鏈接" 最終效果 "最終效果鏈接" 思路 總體 VuePress 在本地完成項目的源文件,推送至 ...
  • 1、環境搭建 基於node.js的http-server伺服器搭建 https://www.npmjs.com/package/http-server cnpm install http-server -g 2、首頁實現 創建一個目錄,叫webapp,在裡面創建一個index.html 打開cmd, ...
  • 利用EasyUI的TreeGrid組件格式化顯示Json數據,首先讀入Json文件,轉成Map對象,迴圈遞歸每一個Map,判斷它的值是基本類型還是Map。如果基本類型,則是屬性節點。如果Map,則是對象,需要再遍歷。 1.Map解析Tree對象 Tree對象 public class Display ...
一周排行
  • 《ASP.NET MVC 企業級實戰》 [作者] (中) 鄒瓊俊[出版] 清華大學出版社[版次] 2017年04月 第1版[印次] 2019年08月 第6次 印刷[定價] 89.00元 【第01章】 (P021) 只有在 Lambda 有一個輸入參數時,括弧才是可選的,否則括弧是必需的。 使用空括弧 ...
  • 上一篇(https://www.cnblogs.com/meowv/p/12971041.html)使用HtmlAgilityPack抓取壁紙數據成功將圖片存入資料庫,本篇繼續來完成一個全網各大平臺的熱點新聞數據的抓取。 同樣的,可以先預覽一下我個人博客中的成品:https://meowv.com/ ...
  • 前言 請了一天假後回公司,同事跟我說使用Newtonsoft.json序列化TreeView對象的時候出現報錯; 啊!什麼?這個類庫不是能夠序列化所有東西嗎?真的很懵逼,也是我第一次使用這個類庫出現問題! 問題異常 異常信息 : Newtonsoft.Json.JsonSerializationEx ...
  • 簡單瞭解下麵詞語的意思 節點:二叉樹中每個元素都稱為節點 葉子節點(簡稱:葉子):度為0的節點,葉子節點就是樹中最底段的節點,葉子節點沒有子節點,也叫終端結點 分枝節點:度不為0的結點 節點的度:二叉樹的度代表某個節點的孩子或者說直接後繼的個數,簡單說就是一個節點擁有的子樹數 樹的度: 樹中最大的結 ...
  • C# 中的LINQ 提供了兩種操作方式,查詢表達式和查詢操作符,所有的查詢表達式都有對應的查操作符類替代,查詢表達式有點“類” SQL,在代碼中寫SQL,總覺得不夠“優雅”,使用查詢操作符就顯得“優雅”很多, 本系列就來對所有的LINQ 標準操作符進行一個全面的總結,這些操作符和我上篇文章總結的Rx ...
  • 在Startup ConfigureServices 註冊本地化所需要的服務AddLocalization和 Configure<RequestLocalizationOptions> public void ConfigureServices(IServiceCollection services ...
  • 為什麼需要持久化,以及Redis持久化的RDB方式在這篇文章講的已經很透徹了,足以弔打面試官了。而且此篇內容需要RDB文章的內容支持,所以建議先看下:看完這篇還不懂Redis的RDB持久化,你們來打我! 一、什麼是AOF 它也是Redis持久化的重要手段之一,aof->Append Only Fil ...
  • 先上圖: @IT程式猿 微博網友評論: @迢書:前同事的,親眼見過 @AvenGeeker:Bug 404 @科技州:這是要逼死強迫症 @小島一瞥:哈哈哈哈哈我老家的車 最後小編整理了一套技術資料不僅能精準消除技術盲點、累計面試經驗,更可以攻剋JVM、Spring、分散式、微服務等技術難題。 海量電 ...
  • 概括來說,分三步: 1,首先找到是哪個進程的CPU占有率飆到了100%。 2,根據進程號pid,定位到是哪個線程,找到對應線程的tid。 3,導出對應線程的dump日誌文件,分析日誌文件定位具體代碼。 要解決這個問題,你應該具備以下技能: 1,linux的top命令。 2,jvm監控工具jps。 3 ...
  • 寫在最後 程式員為何害怕【別人的代碼】呢?這讓我想起一個段子。 寫這段代碼時 只有上帝和我知道他是幹嘛的 現在 只有上帝知道了 別人的代碼,似乎總意味著冗長、晦澀、凌亂,給人一種不想靠近的感覺。搞笑的是,對於一些程式員而言,即使是自己的代碼,在一段時間之後自己再拿來看,也成了【別人的代碼】... 作 ...