计数排序 - 算法数据结构面试分享（五）

数组排序问题 - 计数排序

昨天我们留了一道题目"给你一个整型数组，里面出现的数在[0-100] 之间，能用最优化的方法帮我排序吗"。

1. 确保我们理解了问题，并且尝试一个例子，确认理解无误。

这是一道排序算法题，我们学过很多排序的算法。不一样的是，它给定一个额外的条件，数组里的每个数字都在1-100之间。如果我们采取传统的排序算法，这个条件我们好像用不上。大家在面试的时候如果发现有条件没有用上，基本上我们给出的算法可能不是最优的，或者我们没有解决它最原始的需求。举个例子{50， 46， 50， 0， 100，0} 这个数组中，我们一眼就能看出来 0 有两个， 46有一个，50有两个，100有一个，我们再把他们拼接起来，我们就会得到 {0，0， 46， 50， 50，100}。

2. 想想你可以用什么方法解决问题，你会选择哪一种，为什么？

在上面的分析中我们能够总结出来，我们人工去排序的时候涉及到了两个重要的步骤。1：统计0 - 100 之间每一个数出现的次数: 2： 从0 - 100 的顺序按照他们出现的次数拼接出来。所以现在我们需要解决的问题如何方便计数了。申明一个数字，长度为101，假设50出现了一次，我们就把该数组中下标为50的位置加上1. 全部计数完了，我们再扫描这个数字，将结果写回。
我们现在看一下它的复杂度，我们扫描了原数组一次，又扫描了计数数组一次，所以我们的复杂度是O(n). 这里大家也发现，我们这道题中体现了一个原则，用空间换时间。

3. 解释你的算法和实现的方法

计数部分：扫描原数组， 在index数组中找到对应的位置

int[] indexArray = new int[100];foreach(var e in inputArray){  indexArray[e] ++;}

合并数组部分

int count = 0;for(int index = 0; index < indexArray.Length; index++){if(indexArray[index] > 0 ) //说明index的数字出现过，我们需要拼接起来，出现了几次我们就加几个数 { inputArray[count] = index; count ++; }}

4. 写代码的时候，记住，一定要解释你现在在干什么

那我们就直接上代码啦。

/// 
         /// 给数组排序，该数组里的值在0-100之间         /// 
         ///          public static void IndexSort(int[] array)         {             int[] indexArray = new int[101];             for (var index = 0; index < indexArray.Length; index++)             {                 indexArray[index] = 0;             }             foreach (var e in array)             {                 indexArray[e]++;             }             int count = 0;             for (int index = 0; index < indexArray.Length; index++)             {                 if (indexArray[index] > 0)                 {                     for (int elementCount = 0; elementCount < indexArray[index]; elementCount++)                     {                         array[count++] = index;                     }                 }             }              }  

大家有没有发现，上面的代码其实可以优化，会体现你的基本功哦。要装逼的话可以和面试官提出来的哦。int的默认值是0，所以我们没有必要扫描它一遍给它赋个默认值了。所以这段代码是多余的：

for (var index = 0; index < indexArray.Length; index++)  {     indexArray[index] = 0;  }  

我们来测试一下这个方法：

static void Main(string[] args)    {        int[] array = new int[] { 100, 8, 0, 7, 0, 34 };        IndexSort(array);        foreach(var e in array)        {            Console.Write(e + " " );        }    }  

5. Workthrough

6. 修复缺陷

我们得到的结果:

大功告成了哈。欢迎大家关注我的公众号，还有我的系列专题课程

• 视频教程
• 数据结构与算法
• 经典算法面试题辅导
• 排序专题讲解
• 链表专题讲解

大家有什么更好的解法，也欢迎讨论哈。