基本算法學習(四)之計數排序(JS)

AlexTuan 發布于2019-08-21 11:22 / 3054人閱讀

摘要：計數排序首先我們要對計數排序有一個正確的認識計數排序是用于確定范圍的整數的線性時間排序算法這一句話我們就可以知道計數排序該如何用了處理數據確定范圍內的整數特點快線性時間其數據如下最佳情況最差情況平均情況計數排序的步驟如下查找待排序數組中最大

計數排序

首先我們要對計數排序有一個正確的認識,計數排序是用于確定范圍的整數的線性時間排序算法,這一句話我們就可以知道計數排序該如何用了.
處理數據:確定范圍內的整數
特點:快(線性時間)

其數據如下:
最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n+k)

計數排序的步驟如下

查找待排序數組中最大和最小的元素

統計每個值為i的元素的出現次數

對所有計數開始累加(從min開始,每一項和前一項相加)

反向填充目標數組,將每個元素i放在新數組的第C[i]項,每放一個元素,計數-1.

JS代碼如下:

function countingSort(arr){
  var len = arr.length,
      Result = [],
      Count = [],
      min = max = arr[0];
  console.time("countingSort waste time:");
  /*查找最大最小值,并將arr數置入Count數組中,統計出現次數*/
  for(var i = 0;i= arr[i] ? max : arr[i];
  }
  /*從最小值->最大值,將計數逐項相加*/
  for(var j = min;j=0;k--){
    /*Result[位置] = arr數據*/
    Result[Count[arr[k]] - 1] = arr[k];
    /*減少Count數組中保存的計數*/
    Count[arr[k]]--;
    /*顯示Result數組每一步詳情*/
    console.log(Result);
  }
  console.timeEnd("countingSort waste time:");
  return Result;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(countingSort(arr));

運行結果為:
[ , , , , , , , , , , , , , 48 ]
[ , , , , , , , , , , , , , 48, 50 ]
[ , , , , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
countingSort waste time:: 14ms
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]

仔細看代碼就知道其實過程很簡單,但是個人認為編碼時的關鍵在于理解最后反向填充時的操作.

GPU云服務器云服務器學習排序算法 JS排序算法計數排序 php基本排序

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

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

【算法】計數排序 + 各個排序算法的穩定性

摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。之前介紹的排序算法：【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...

不知名網友 2021-11-29 10:50 評論0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...

verano 2019-08-20 15:08 評論0 收藏0
常用排序算法之JavaScript實現

摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

jerry 2019-08-21 12:27 評論0 收藏0
Javag工程師成神之路（2019正式版）

摘要：結構型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態模式策略模式職責鏈模式責任鏈模式訪問者模式。主要版本更新時間備注 v1.0 2015-08-01 首次發布 v1.1 2018-03-12 增加新技術知識、完善知識體系 v2.0 2019-02-19 結構...

Olivia 2019-08-16 15:14 評論0 收藏0