數據結構—各類‘排序算法’實現（下）

       在上一篇博客中，主要是實現各種的排序算法，并針對一些算法進行了優化的處理，下面主要討論一下非比較排序的算法（計數排序、基數排序），同時并對各種排序算法的性能、時間復雜度、空間復雜度、優缺點、以及適用場景做總結分析。

1.計數排序

         主要思想：主要是需要統計次數，使用直接定址法，統計最大數和最小數，開辟兩個數相差的空間大小，對于重復數據，使用count用來計數,時間復雜度O(N+范圍個數)，空間復雜度O(范圍個數)計數排序適合于數據較為密集的情況，當數據密集且沒有重復的數據，可以直接使用‘位圖’，更能夠省下空間

void CountSort(int* a, size_t size)
{
     assert(a);
     int max = a[0];
     int min = a[0];
     int count = 0;
 
     for (size_t i = 0; i < size; ++i)      //尋找數組中的最大數和最小數
     {
          if (a[i] < min)
          {
               min = a[i];
          }
          if (a[i] > max)
          {
               max = a[i];
          }
     }
     
     int* tmp = new int[max - min + 1];    //開辟存儲空間,并初始化
     memset(tmp, 0, sizeof(int)*(max - min + 1));
     for (size_t i = 0; i < max - min + 1; ++i)   //直接定址法
     {
          int num = a[i] - min;
          tmp[num]++;
     }
     for (size_t i = 0; i < size;)    //將排序好的順序寫入a數組中
     {
          for (size_t j = 0; j < max - min + 1; ++j)
          {
               count = tmp[j];
               while (count--)    //對于重復數據需要多次進行寫入
               {
                    a[i] = j + min;
                    i++;
               }
          } 
     }
     delete[] tmp;
}

2.基數排序

        主要思想：和‘快速轉置’的思想相像，開辟兩個數組count和start，count用來統計個位上分別為0~9的數據個數，start用來統計數據的開始位置（起始位置為0，下一位的數據開始的位置=上一個數據的開始位置+上一位總的數據個數），另開辟size大小的空間來存放每次排序，下面是低位基數排序，從個位開始排序，然后排序十位，進而百位，直到排到最大數據的最高位，排序結束。

int GetMaxRadix(int* a, size_t size)    //尋找最大數據的位數
{
     int index = 1;   //數據最小有一位
     int max = 10;
     for (size_t i = 0; i < size; ++i)
     {
          while (a[i] >= max)      //數據大于1位
          {
               index++;
               max = max * 10;
          }
     }
     return index;
}

void LSDSort(int* a, size_t size)
{
     assert(a);
     int index = GetMaxRadix(a, size);   //求最大數據的位數
     int count[10] = { 0 };    //記錄數據出現的次數
     int start[10] = { 0 };   //記錄數據的開始位置
     int radex = 1;
     int* bucket = new int[size];   
     
     for (int k = 1; k <= index; ++k)    //從各位到最高位排序
     {
          memset(count, 0, sizeof(int)* 10);    //每次排序之前需將count置0
          //計數（各位分別為0~9的數據個數）
          for (size_t i = 0; i < size; ++i)
          {
               int num = (a[i] / radex) % 10;     //取個位
               count[num]++;
          }
          
          //記錄數據開始的位置
          start[0] = 0;
          int j = 1;
          while (j < 10)
          {
               start[j] = start[j - 1] + count[j - 1];
               j++;
          }
          for (size_t i = 0; i < size; ++i)   //將數據按順序放入bucket中
          {
               int num = (a[i] / radex) % 10;
               bucket[start[num]++] = a[i];
          }
          radex *= 10;
          memcpy(a, bucket, sizeof(int)* size);
     }    
     delete[] bucket;
}

3.排序算法總結

（1）各種排序算法的性能分析

 其中：r為數據范圍的個數 

穩定性分析：

        穩定性：指的是需要排序的數據之中如果有相同的數據元素，在排序前、后的相對位置是不變的，即就是當排序{1,3,5,7,2,5,6}，通過排序后‘5’在'5'之前，而不是相互交換了。

         在介紹的這幾種排序之中插入排序、冒泡排序、歸并排序、計數排序是穩定的。快速排序、希爾排序、選擇排序、堆排序是不穩定的

空間復雜度：

        排序算法中，快速排序（需要進行遞歸）、歸并排序、計數排序、基數排序都是需要額外的空間進行排序。其余的排序算法就不需要借助任何的空間。

時間復雜度：

 O(N^2)：

        插入排序、冒泡排序、選擇排序都是空間復雜度為O(N^2)，排序效率基本上都是比較低，選擇排序是最不好的，因為在最有的情況下，也需要N^2的時間復雜度，相對來說，插入和冒泡能好一點，在優化的情況下，能夠減少排序的時間。但是當數據量較大時，冒泡的時間代價會更高。

O(N*lgN)：

       平均性能為O(N*lgN)的算法：快速排序、歸并排序、堆排序算法，快速排序經過各種的優化算法（三數取中法、區間較小時利用直接插入算法，【上篇博客中詳細的介紹了快速排序的優化】）已經相對來說效率提高了很多。

       歸并排序又稱為外排序，外排序其實就是指能夠對內存之外（磁盤中）數據進行排序，對于大數據的文件，不能夠直接加載到內存中進行排序，我們可以采取將文件劃分成小文件，將小的文件加載到內存中進行排序，然后將排好序的數據進行重寫，將兩個有序的數據文件在重新排序，就能夠排好大數據文件。這個讀者可以下去進行試驗，這里就不做詳細的解釋。

       堆排序的效率雖然還是挺高的，但是堆排序有個致命的缺點，就是只能夠對數組進行排序，因為需要通過數組的下標來確定數據在堆中的具體位置。所以堆排序只能對數組進行排序。