计数排序不是面试常见的问题，但是我们写题的时候经常会用到计算统计数组的计数排序步骤和最终元素放置的思想，比如就地替换，使用arrays来模拟hashmap等等，所以还是很重要的。有必要看一看。今天我们就来看看线性排序中的计数排序到底是怎么一回事。我们把镜头切到元记餐厅，因为元记餐厅今年的福利不错，所以元厨想给员工一些小福利，让小二按照工龄来排序。不过，这家餐厅总共有10万名员工，而且这家餐厅已经开了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，我们暂且这么理解，后面再优化。我们继续上图的例子来说明，在这个数组中，索引代表元素值（即上例中的服务时长），数组的值代表元素个数（即,不同工龄的出现次数)。即，有1个工龄为0的员工、1个工龄为1的员工和3个工龄为2的员工。..然后我们按照出现的次数依次取出来，看看效果如何。0,1,2,2,2,3,4,5,5,9我们发现此时元素已经变成有序的了，但这并不是排序，只是简单的根据统计数组元素的下标输出值，并且实际上并不对原始数组进行排序。这样操作之后，我们就不知道这个工龄属于哪个员工了。看下图的例子，虽然苗和杰的工龄相同，但是如果我们按照上面的操作输出，我们无法知道工龄为4的两个员工谁是苗，谁是杰。所以我们需要使用其他方法对元素进行排序。还记得我们之前提到的前缀和吗，我们通过上面的计数次数数组来求前缀和数组。既然我们通过统计次数的数组得到了前缀和数组，那我们就来分析一下presum数组中的值的含义。比如我们的presum[2]=5表示原数组中有5个值小于等于2，presum[4]=7表示有7个元素小于等于4。是不是觉得计数排序的意义会逐渐浮现？其实到这里我们也能理解的差不多了，还是少了最后一步。这时候我们需要从后往前遍历原数组，然后将遍历到的元素放到临时数组的合适位置，并修改presum数组的值，遍历结束后，目的排序实现。这时候有人就要问了，为什么要从后面遍历到前面呢？这个问题的答案，回头再说，我们继续往下看。计数排序，我们从后往前遍历，nums[9]=9，然后取值到presum数组中查找，发现presum[nums[9]]=presum[9]=10、大家还记得我们的presum数组中每个值是什么意思吗？此时presum[9]=10，也就是说数组中有10个小于等于的数，所以我们需要把他排在临时数组的第10位，也就是temp[9]=9.我们还需要做什么？大家想一想，我们已经把9放到temp数组里排序了，那我们的presum数组就不要再统计他了，然后把对应位置减1即presum[9]=10-1=9;接下来，我们继续遍历5，然后进行同样的上诉步骤。我们继续查询presum数组，发现presum[5]=9，也就是说有9个数小于等于5，我们把它放到temp数组的第9位，也就是temp[8]=5.然后将presum[5]减1。这里的计数和排序的大概思路你明白了吗？那么为什么我们需要从后面遍历到前面呢？让我们考虑一下。如果我们从前向后遍历，如果相同的元素相同，则先返回前一个元素再减一，这样就会使计数排序变成不稳定排序。算法。这个排序过程看起来像查字典吗？通过查询presum数组，您可以找出您应该在临时数组中的哪个位置。然后修改字典，直到遍历结束。那么我们先用动画来模拟一下我们bug版本的统计和排序，加深一下理解。注：动画中省略了获取预置数组的过程。直接模拟排序过程。但是现在结束了吗？显然不是，我们想想这种情况。如果我们的数字是90,93,94,91,92如果我们按照上面的方法设置presum数组的长度，那么我们需要将数组的长度设置为95（因为最大值是94），这显然是不合理的，会浪费很多空间。当我们需要对负数进行排序时也会出现一个问题，因为我们在计算次数的时候，是根据nums[index]的值来填充presum数组的，所以当nums[index]为负数时，在填充presum的时候array会报错。这时候用最大值来定义数组的长度就不合理了。所以我们需要采取另一种方式来定义数组长度。先说一下offset的概念。比如90、93、94、91、92，我们可以通过max和min的值来设置数组长度，即94-90+1=5。偏移量就是min值，也就是90。那么我们的90对应于索引0。见下文。这样我们在填充presum数组的时候，就不会浪费空间了。负数？当然，负数也是可能的。继续看例子：-1,-3,0,2,1是一样的，哦，到这里我们已经完成了计数和排序，我们来看代码。classSolution{publicint[]sortArray(int[]nums){intlen=nums.length;if(nums.length<1){returnnums;}//求最大值和最小值intmax=nums[0];intmin=nums[0];for(intx:nums){if(max
