排序真的不重要？

序虽然不是面试常考题目，但是计数排序的求统计数组步骤和最后元素归位思想是我们刷题时经常用到的，例如原地置换，使用数组模拟 hashmap 等，所以还是很有必要看一下的。

今天我们就一起来看看线性排序里的计数排序到底是怎么回事吧。

我们将镜头切到袁记菜馆

因为今年袁记菜馆的效益不错，所以袁厨就想给员工发些小福利，让小二根据员工工龄进行排序，但是菜馆共有 100000 名员工，菜馆开业 10 年，员工工龄从 0 - 10 不等。

看来这真是一个艰巨的任务啊。

当然我们可以借助之前说过的 归并排序 和 快速排序 解决，但是我们有没有其他更好的方法呢?

了解排序算法的老哥可能已经猜到今天写什么啦。是滴，我们今天来写写用空间换时间的线性排序。

说之前我们先来回顾一下之前的排序算法，最好的时间复杂度为 O(nlogn) ,且都基于元素之间的比较来进行排序。

我们来说一下非基于元素比较的排序算法，且时间复杂度为 O(n)，时间复杂度是线性的，所以我们称其为线性排序算法。

其优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)，此时的 k 则代表整数的范围。快于任何一种比较类排序算法，不过也是需要牺牲一些空间来换取时间。

下面我们先来看看什么是计数排序，这个计数的含义是什么?

我们假设某一分店共有 10 名员工，

工龄分别为 1，2，3，5，0，2，2，4，5，9

那么我们将其存在一个长度为 10 的数组里，，但是我们注意，我们数组此时存的并不是元素值，而是元素的个数。见下图

时我们这里统计次数的数组长度根据最大值来决定，上面的例子中最大值为 9 ，则长度为 9 + 1 = 10。暂且先这样理解，后面会对其优化 。

我们继续以上图的例子来说明，在该数组中，索引代表的为元素值(也就是上面例子中的工龄)，数组的值代表的则是元素个数(也就是不同工龄出现的次数)。

即工龄为 0 的员工有 1 个， 工龄为 1 的员工有 1 个，工龄为 2 的员工有 3 个 。。。

然后我们根据出现次数将其依次取出看看是什么效果。

0，1，2，2，2，3，4，5，5，9

我们发现此时元素则变成了有序的，但是这并不是排序，只是简单的按照统计数组的下标，输出了元素值，并没有真正的给原始数组进行排序。

这样操作之后我们不知道工龄属于哪个员工。

见下图

然喵哥和杰哥工龄相同，如果我们按照上面的操作输出之后，我们不能知道工龄为 4 的两个员工，哪个是喵哥哪个是杰哥。

所以我们需要借助其他方法来对元素进行排序。

大家还记不记得我们之前说过的前缀和，下面我们通过上面统计次数的数组求出其前缀和数组。

（编辑：宁德站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!