排序算法:计数排序

icy2003 程序 2020-05-22 15:16:33 125 0条

计数排序是一个非基于比较的排序算法,该算法于 1954 年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为 Ο(n+k)(其中 k 是整数的范围),快于任何比较排序算法

640 (3).gif

算法评价

  • 平均时间复杂度:O(n + k)
  • 最好情况:O(n + k)
  • 最坏情况:O(n + k)
  • 空间复杂度:O(k)
  • 稳定性:稳定

算法思想

  1. 找出待排序的数组中最大和最小的元素。
  2. 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项。
  3. 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加)。
  4. 向填充目标数组:将每个元素 i 放在新数组的第 C[i] 项,每放一个元素就将 C[i] 减去 1。

代码示例

Javascript

Array.prototype.countSort = function() {
    let len = this.length
    if (len < 2) {
        return
    }
    // 桶数组
    var suportArr = new Array(len + 1);
    // 结果数组
    var resArr = new Array(len);
    // 初始化桶数组
    for (i = 0; i < suportArr.length; i++) {
        suportArr[i] = 0;
    }
    // 待排序数组中的数组出现,在桶子对应位置+1代表这个数出现的个数+1了
    for (let i = 0; i < len; i++) {
        suportArr[arr[i]]++;
    }
    // 从第1项开始,桶数组加上前一个桶的个数,现在辅助数组的意义变成了每一项的排名了。
    for (let i = 1; i < suportArr.length; i++) {
        suportArr[i] += suportArr[i - 1];
    }
    // 根据辅助数组的排名,从后往前赋值
    for (let i = len - 1; i >= 0; i--) {
        resArr[suportArr[arr[i]] - 1] = arr[i];
        suportArr[arr[i]]--;
    }
    // 这里this不能直接赋值数组,我们就只能采取splice剪切数组再替换新的
    this.splice(0, this.length, resArr)
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。