計數排序 - 算法數據結構面試分享（五）

數組排序問題 - 計數排序

昨天我們留了一道題目“給你一個整型數組，里面出現的數在[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. 寫代碼的時候，記住，一定要解釋你現在在干什么

那我們就直接上代碼啦。

/// <summary>  
       /// 給數組排序，該數組里的值在0-100之間  
       /// </summary>  
       /// <param name="array"></param>  
       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. 修復缺陷

我們得到的結果:

大功告成了哈。歡迎大家關注我的公眾號，還有我的系列專題課程

• 視頻教程
• 數據結構與算法
• 經典算法面試題輔導
• 排序專題講解
• 鏈表專題講解

大家有什么更好的解法，也歡迎討論哈。