原文链接

简介

算法总是依赖输入数据。我们看过一般意义上的排序算法,比如插入排序,冒泡排序和快速排序,他们在某些情况下非常高效而某些情况下则不然。诚然,插入和冒泡排序是很慢的(平均复杂度O(n^2)),但是在输入数据基本有序的情况下,他们却非常高效。换句话说,如果你有一个已经排序的数组,在添加一些新数据后,使用插入排序可以高效的完成任务。另一方面,尽管快速排序在处理随机数据时表现非常好,但是在实践中当数据基本有序时,他会表现得和冒泡排序一样慢。

现在我们知道算法执行效率的高低依赖于输入数据。对于大多数有序数据来说,我们更倾向于插入排序而不是快速排序(虽然一般来说它很快)。

因为输入数据对于排序算法效率来说是如此的重要,我们不禁要问是否存在一种排序算法它比O(n*log(n))更快呢?我们的回答是:存在。有一些拥有线性复杂度的算法,他们比快速排序,插入排序,堆排序更快。但是使用他们的场合是有限制的。

我们不可能在线性的时间里对于任何数据进行排序,所以问题就集中在符合什么规则的数据可以在线性时间内排序。

这样一个可以在线性O(n)时间里排序数据的算法就是计数排序,它只能对于整数进行排序

概述

假设我们有一个乱序的整数数组。它仅仅包含整数而且它以整数作为排序的依据,所以我们实现计数排序

首先创建一个临时数组(长度为输入数据的最大间隔),对于每一个输入数组的整数k,我们在临时数组的第k位置"1"。

enter image description here

注意上图中,第一行表示输入数据,第二行表示创建的临时数据,
临时数组的下标代表输入数据的某一个值,临时数组的值表示输入数据中某一个值的数量。

如果输入数据中有重复的数值,那么我们增加临时数组相应的值(比如上图中5有3个,所以小标为5的数组的值是3)。在“初始化”临时数组以后,我们就得到了一个排序好的输入数据。

enter image description here 我们顺序遍历这个数组,将下标解释成数据, 将该位置的值表示该数据的重复数量,记得得到一个排序号的数组。

实现

实际上,实现计数排序是非常简单的。需要注意的是老的编程语言不是很灵活而且我们需要初始化整个临时数组。这样就导致了另一个问题:我们必须知道输入数据的间隔。幸运的是现在的编程语言和库更加的灵活,所以我们可以初始化一个临时数组而不需要知道数据的最大间隔(如下例所示)。PHP非常灵活,它可以在不预先知道数据长度的情况下创建数组,但是我们仍然必须进行ksort

$list = array(4, 3, 5, 9, 7, 2, 4, 1, 6, 5);

function radix_sort($input)
{
    $temp = $output = array();
    $len = count($input);

    for ($i = 0; $i < $len; $i++) {
        $temp[$input[$i]] = ($temp[$input[$i]] > 0) 
            ? ++$temp[$input[$i]]
            : 1;
    }

    ksort($temp);

    foreach ($temp as $key => $val) {
        if ($val == 1) {
            $output[] = $key; 
        } else {
            while ($val--) {
                $output[] = $key;
            }
        }
    }

    return $output;
    }

// 1, 2, 3, 4, 4, 5, 5, 6, 7, 9
print_r(radix_sort($list));

上面代码的问题是PHP需要进行ksort,当我们尝试用另一个排序算法去排序数组时,但是要克服这点的话,你就必须提前知道数组的最大长度然后创建一个全0的临时数组,正如下面的例子所示。

define(MIN, 1);
define(MAX, 9);
$list = array(4, 3, 5, 9, 7, 2, 4, 1, 6, 5);

function radix_sort(&$input)
{
    $temp = array();
    $len = count($input);

    // initialize with 0s
    $temp = array_fill(MIN, MAX-MIN+1, 0);

    foreach ($input as $key => $val) {
        $temp[$val]++;
    }

    $input = array();
    foreach ($temp as $key => $val) {
    if ($val == 1) {
        $input[] = $key;
    } else {
        while ($val--) {
            $input[] = $key;
        }
    }
    }
}

// 4, 3, 5, 9, 7, 2, 4, 1, 6, 5
var_dump($list);

radix_sort(&$list);

    // 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
    var_dump($list);

这个例子中输入数组被修改用作最后的排序结果。

复杂度

计数排序的复杂度是线性的,用大O记号表示就是O(n)。相比O(n.log(n))和更糟的O(n2)来说非常大的提高。

enter image description here

为什么使用计数排序? 1. 它非常快

计数排序相比其他算法来说要快很多(正如上图所示)。这个算法在实际使用中非常实用,因为实践中经常需要排序整数。

enter image description here

2. 理解简单,实现容易

即便是一个初学者也能明白和实现计数排序。你不需要更多的循环来实现他们。

为什么不使用计数排序

1. 只适用于整数

如果你不了解输入数据,最好不要使用计数排序。我们可能认为我们的输入只是整数所以就用计数排序,但是如果以后有人传了浮点数或者是字符串怎么办呢。

enter image description here

2. 需要额外空间

Radix需要额外的空间(至少和输入数据一样多)

后话

虽然计数排序收到输入领域的限制,但是我必须要说在实践中,有大量情况只是用来排序整数。比如当我们从数据库里使用主键取数据时 -- 一般来说数据库表的主键通常都是整数。因此,实践中有很多情况需要排序整数,计数排序或许是一个非常使用的算法而且它也非常酷又易于实现。

相关文章: 1. Computer Algorithms: Shell Sort 2. Computer Algorithms: Merge Sort 3. Algorithm Cheatsheet: Radix Sort

附录(文中概念的通俗注释) 什么是线性时间? 线性(linear)是一个数学上的术语,表示量与量之间存在着固定的比例关系。比如我们说“跳远关于身高是线性关系”,含义就是如果身高是x厘米,那么跳远就是x厘米K倍(这里K是固定值),用通俗化例子,如果身高170那么跳远距离就是170的1.5倍。当然由于这个属于比较通用,所以大多数书籍中在提及“线性”时不会很明确的指明是【什么】和【什么】存在线性关系,这些内容都包含在讨论的上下文里。

还有什么与“线性”相关的术语? 对数关系(logarithmic):身高170,跳远距离是 log(170) 多项式关系(polynomial):身高170,跳远距离 170^2 + 170 + 3 指数关系(exponetial):身高170,跳远距离2^170 阶乘关系(factorial):身高170,跳远距离 170!

算法运行时间与复杂度 上文中其实是指【算法运行的时间】关于【算法的输入数据的个数】是线性关系。举个例子来说:输入100个数据,那么算法可以再100的K倍时间完成。

又由于【算法运行的时间】是由【算法的复杂度】来衡量的,【算法的复杂度】复杂度用通俗化来讲就是算法【大概要计算多少次】。对于【算法的复杂度】来说,他不是一个精确的值,而是表示某个规模。比如输入100个数据,一个做100 x 3=300次比较的算法与100 x 5=500次比较的算法,从【算法的复杂度角度】来看,他们是相同的,他们都是O(n),其中n表示算法的输入。但是如果一个是100的“平方”次的比较算法,那么他与之前两个算法的复杂度是不同的,平方次的算法复杂度是O(n^2)。

【算法运行的时间】和【算法的复杂度】基本表示的是一个意思,因为对于有一定算法了解的人来说,他们都是说的一件事情。

译者的后话 1.原文作者搞错了算法的名字,原文是radix sort但是文章的内容却是counting sourt,所以我将其中的算法名字改了。

2.这个算法的使用作为学习hash思想的材料还不错,实用性不高,首先大多数对象以整数为排序依据,但是排序的对象不是整数和是对象本身,所以这里的数据要改成桶+链表的hash表。第二数据的间隔可能导致元素数组和临时数据大小相差巨大,比如排序1,65535,你就需要开65535的数组,当然你可以使用hash表,但是hash表是无序的,正如第一个算法实现的那样,hash本身的键值还需要排序。在现代的没有整数上限的脚本语言里这个算法基本没法发挥。

3.在工程项目里,尽量避免自己去实现一些通用算法,尽量使用标准库自带的。(从二分算法提出到第一个完全正确的代码实现中间相隔好几年!)

4.补充我写的一篇简单文章:三言两语说清【基数排序】与【计数排序】 相关阅读:

插入排序:排序过的数据能显著改善程序运行速度

分久必合 -- 图说归并排序