排序算法(一)计数排序

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

在做前端工作的时候常常会对数组做处理,也经常会用到排序,今天开始将对常用排序算法做总结,顺便复习一些数据结构知识。
友情提示:阅读本文大概需要 22分钟

前言

计数排序,是一种比O(nlogn)还快的排序方式,大家熟知的冒泡排序、快速排序等都是基于元素之间的比较进行排序,而计数排序独辟蹊径,通过利用数组的下标来确定元素的正确位置从而实现排序。

当我们学习排序或者应用排序的时候,不应也不能只追求结果而忽略算法实现的时间、成本和性能,尤其是对JS这门较慢的语言而言,因此在研究排序算法时,我们需要计算比较和交换的数量。对于不交换元素的算法,还需要考虑访问数组的次数。

计数排序

题目背景

假定有一个数组,里面存有20个随机整数:

var array = [9354912781365340109 ,79]

如何实现排序呢? 

最简单的实现方式是:先遍历这个无序的随即数组,每一个整数按照其值对号入座,对应数组下标的元素进行加 1 操作。比如这个数组的第一个整数是 9(array[0]),那么数组下标为9的元素加 1,第二个整数是 3,那么数组下标为3的元素加 1,依次遍历该数组。当全部遍历完成之后,数组的状态如:

value:
1 2 1 3 2 2 1 2 1 4 1
// 数组每一个下标位置的值,代表了数列中对应整数出现的次数
index:
0 1 2 3 4 5 6 7 8 9 10

根据第一次遍历处理后的统计结果再次进行排序,直接遍历数组。

// 输出数组元素的下标值,元素的值是几就输出几次
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10

由此便能得到一个有序的数组。这就是计数排序算法的简易版排序过程,它适用于一定范围内的整数排序。(此demo 案例来源于 程序员小灰的文章demo,地址是:https://mp.weixin.qq.com/s/WGqndkwLlzyVOHOdGK7X4Q)。


实现思路

在实际的业务中,我们不会以数列的最大的值作为统计数据的长度,为了避免过多冗余的计算量,一般以数组的最大值和最小值的差+1 作为统计数组的长度。同时将数组的最小值作为一个偏移量,用于统计数组的对号入座。比如

75 74 71 79 78 70 79 73 72 71
// 统计数组的长度:79-70+1 = 10
// 偏移量:70(数组的最小值)

对于这个数组的第一个整数 75,对应的统计数组的下标就是 75 - 70 = 5;此时,为了区别和避免某些数值相同的情况,我们从统计数组的第二个元素开始,每个元素都加上前面的元素之和,这样一方面既保障了原排序数组的顺序,又方便区别数组元素值相同而无法区分的情况。

Q:如果原始数组的规模是N,最大最小整数的差值是M,求计数排序的时间复杂度和空间复杂度?

A:代码第1、2、4步都涉及遍历原始数组,运算量均是N,第3步遍历统计数组,运算量是M,所以总体运算量是3N+M,时间复杂度是O(N+M);不考虑结果数组而只考虑数组大小的话,空间复杂度是O(M)。


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<len;i++){
    Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
  }
  // 从最小值->最大值,将计数逐项相加
  for(var j = min;j<max;j++){
    Count[j+1] = (Count[j+1]||0)+(Count[j]||0);
  }
  // Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据
  for(var k = len - 1;k>=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));
C++实现
void CountSort(int arr[],int nLength)
{
    int *pCount = NULL;
    int i;
    int j;
    int nMin,nMax;

    if(arr == NULL || nLength <=0)return;

    // 找最大值和最小值
    nMax = arr[0];
    nMin = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] > nMax)
        {
            nMax = arr[i];
        }
        if(arr[i] < nMin)
        {
            nMin = arr[i];
        }
    }
    // 开辟计数数组
    pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));
    memset(pCount,0,sizeof(int ) * (nMax-nMin+1));
    // 计数
    for(i = 0;i<nLength;i++)
    {
        pCount[arr[i]-nMin]++;
    }
    // 放回原数组
    j = 0;
    for(i = 0;i< nMax-nMin+1;i++)
    {
        while(pCount[i] != 0)
        {
            arr[j] = i+nMin;
            j++;
            pCount[i]--;
        }
    }
}

总结

局限性:

时间复杂度是O(N+M),当数组最大值和最小值差值过大时,不适用计数排序;当数组元素不是整数时,不适用计数排序。

小知识

Q: 为什么很多编程语言(如C++、Java、JS)的数组的起始索引是 0 而不是 1 ?(前面文章介绍的Lua语言的起始索引是1)

A: 这个习惯来源于机器语言,那时要计算一个数组元素的地址需要将数组的起始地址加上该元素的索引。将起始索引设为 1 要么会浪费数组的第一个元素的空间,要么会花费额外的时间来将索引减 1。

最后

今天的 排序算法之计数排序 就分享到这里,有问题欢迎大家留言,谢谢 ~ 

原文始发于微信公众号(程序员思语):排序算法(一)计数排序