基本算法学习(四)之计数排序(JS)

AlexTuan 发布于2019-08-21 11:22 / 3053人阅读

摘要：计数排序首先我们要对计数排序有一个正确的认识计数排序是用于确定范围的整数的线性时间排序算法这一句话我们就可以知道计数排序该如何用了处理数据确定范围内的整数特点快线性时间其数据如下最佳情况最差情况平均情况计数排序的步骤如下查找待排序数组中最大

计数排序

首先我们要对计数排序有一个正确的认识,计数排序是用于确定范围的整数的线性时间排序算法,这一句话我们就可以知道计数排序该如何用了.
处理数据:确定范围内的整数
特点:快(线性时间)

其数据如下:
最佳情况：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基本排序

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

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