javascript计数排序

in 算法 with 0 comment

计数排序

计数排序是一个线性排序，但有其使用场景，如果原数列有n个元素，最大值和最小值差为m, 时间复杂度为O(n+m), 空间复杂度为：O(m), 是一种稳定排序

初级计数排序（非修改原数组，不稳定）

//计数排序是一种线性排序，时间复杂度O(n)
const selectionSortArr = [9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9]
function countSort(arr) {
  //找出数组的最大值
  let maxVal = arr[0]
  for(let k = 0; k < arr.length; k++) {
    if(arr[k] > maxVal) {
      maxVal = arr[k]
    }
  }
  let m_arr = new Array(maxVal + 1).fill(0) 
  let result = []
  for(let i = 0; i < arr.length; i++) {
    m_arr[arr[i]]++
  }
  for(let i = 0; i < m_arr.length; i++){
    for(let j = 0; j < m_arr[i]; j++){
      result.push(i)
    }
  }
  return result
}
let res = countSort(selectionSortArr)
console.log(res)

计数排序升级（非修改原数组，不稳定）

如果数组是这样的 [95, 94, 91, 98, 99, 90, 99, 93, 91, 92]，这时如果按最大值+1构造数组的话，需要构建一个100个长度的数组，这样大部分空间都是浪费的，做法就是构建一个 length = maxVal - minVal + 1 的数组，同时以minVal为基准所有元素减去minVal计算元素的下标, 因为数组下标都是从0开始的

function countSort(arr) {
  //找出数组的最大值与最小值
  let maxVal = arr[0], minVal = arr[0]
  for(let k = 0; k < arr.length; k++) {
    if(arr[k] > maxVal) {
      maxVal = arr[k]
    }
    if(arr[k] < minVal) {
      minVal = arr[k]
    }
  }
  //console.log(maxVal, minVal)
  //构造一个length = maxVal - minVal + 1 的数组，这样就不会浪费
  let m_arr = new Array(maxVal - minVal + 1).fill(0)  
  let result = []
  for(let i = 0; i < arr.length; i++) {
    //以minVal为步长，所有元素值减去minVal放数组中
    m_arr[arr[i] - minVal]++
  }
  for(let i = 0; i < m_arr.length; i++){
    for(let j = 0; j < m_arr[i]; j++){
      //取回值的时候再加上minVal
      result.push(i + minVal)
    }
  }
  return result
}
let res = countSort(selectionSortArr)
console.log(res)

计数排序升级（非修改原数组，稳定）

以上两种方法都是直接输出对应的构造数组中的值进行排序，这种排序不稳定，如果遇到比如排序成绩，小灰,小黄，小红，小白，小绿， 成绩依次:[90,99,95,94,95],上边的做法就没法判断成绩一样的谁是谁了，为了解决这个问题，对m_arr数组进行变形

function countSort(arr) {
  //找出数组的最大值与最小值
  let maxVal = Math.max(...arr)
  let minVal = Math.min(...arr)
  //console.log(maxVal, minVal)
  //构造一个length = maxVal - minVal + 1 的数组，这样就不会浪费
  let m_arr = new Array(maxVal - minVal + 1).fill(0)  
  for(let i = 0; i < arr.length; i++) {
    //以minVal为步长，所有元素值减去minVal放数组中
    m_arr[arr[i] - minVal]++
  }
  //将m_arr变形，每个元素的值为当前元素的值加上上一个元素的值
  //加后的值表示原数组中元素所在的位置
  for(let j = 1; j < m_arr.length; j++) {
    m_arr[j] = m_arr[j] + m_arr[j - 1]
  }
  //result数组与原数组arr长度相同
  let result = []
  for(let m = arr.length - 1; m >= 0; m --) {
    let index =  m_arr[arr[m] - minVal]
    result[index - 1] = arr[m]
    m_arr[arr[m] - minVal]--
  }
  return result
}
let res = countSort(selectionSortArr)
console.log(res)

本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 22, 2021 at 16:59 pm
转载请注明来源

评论已关闭.