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)
评论已关闭.