數(shù)據(jù)結(jié)構(gòu)—各類‘排序算法’實(shí)現(xiàn)（下）

       在上一篇博客中，主要是實(shí)現(xiàn)各種的排序算法，并針對(duì)一些算法進(jìn)行了優(yōu)化的處理，下面主要討論一下非比較排序的算法（計(jì)數(shù)排序、基數(shù)排序），同時(shí)并對(duì)各種排序算法的性能、時(shí)間復(fù)雜度、空間復(fù)雜度、優(yōu)缺點(diǎn)、以及適用場(chǎng)景做總結(jié)分析。

1.計(jì)數(shù)排序

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

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)      //尋找數(shù)組中的最大數(shù)和最小數(shù)
     {
          if (a[i] < min)
          {
               min = a[i];
          }
          if (a[i] > max)
          {
               max = a[i];
          }
     }
     
     int* tmp = new int[max - min + 1];    //開辟存儲(chǔ)空間,并初始化
     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;)    //將排序好的順序?qū)懭隺數(shù)組中
     {
          for (size_t j = 0; j < max - min + 1; ++j)
          {
               count = tmp[j];
               while (count--)    //對(duì)于重復(fù)數(shù)據(jù)需要多次進(jìn)行寫入
               {
                    a[i] = j + min;
                    i++;
               }
          } 
     }
     delete[] tmp;
}

2.基數(shù)排序

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

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

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

3.排序算法總結(jié)

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

 其中：r為數(shù)據(jù)范圍的個(gè)數(shù) 

穩(wěn)定性分析：

        穩(wěn)定性：指的是需要排序的數(shù)據(jù)之中如果有相同的數(shù)據(jù)元素，在排序前、后的相對(duì)位置是不變的，即就是當(dāng)排序{1,3,5,7,2,5,6}，通過(guò)排序后‘5’在'5'之前，而不是相互交換了。

         在介紹的這幾種排序之中插入排序、冒泡排序、歸并排序、計(jì)數(shù)排序是穩(wěn)定的。快速排序、希爾排序、選擇排序、堆排序是不穩(wěn)定的

空間復(fù)雜度：

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

時(shí)間復(fù)雜度：

 O(N^2)：

        插入排序、冒泡排序、選擇排序都是空間復(fù)雜度為O(N^2)，排序效率基本上都是比較低，選擇排序是最不好的，因?yàn)樵谧钣械那闆r下，也需要N^2的時(shí)間復(fù)雜度，相對(duì)來(lái)說(shuō)，插入和冒泡能好一點(diǎn)，在優(yōu)化的情況下，能夠減少排序的時(shí)間。但是當(dāng)數(shù)據(jù)量較大時(shí)，冒泡的時(shí)間代價(jià)會(huì)更高。

O(N*lgN)：

       平均性能為O(N*lgN)的算法：快速排序、歸并排序、堆排序算法，快速排序經(jīng)過(guò)各種的優(yōu)化算法（三數(shù)取中法、區(qū)間較小時(shí)利用直接插入算法，【上篇博客中詳細(xì)的介紹了快速排序的優(yōu)化】）已經(jīng)相對(duì)來(lái)說(shuō)效率提高了很多。

       歸并排序又稱為外排序，外排序其實(shí)就是指能夠?qū)?nèi)存之外（磁盤中）數(shù)據(jù)進(jìn)行排序，對(duì)于大數(shù)據(jù)的文件，不能夠直接加載到內(nèi)存中進(jìn)行排序，我們可以采取將文件劃分成小文件，將小的文件加載到內(nèi)存中進(jìn)行排序，然后將排好序的數(shù)據(jù)進(jìn)行重寫，將兩個(gè)有序的數(shù)據(jù)文件在重新排序，就能夠排好大數(shù)據(jù)文件。這個(gè)讀者可以下去進(jìn)行試驗(yàn)，這里就不做詳細(xì)的解釋。

       堆排序的效率雖然還是挺高的，但是堆排序有個(gè)致命的缺點(diǎn)，就是只能夠?qū)?shù)組進(jìn)行排序，因?yàn)樾枰ㄟ^(guò)數(shù)組的下標(biāo)來(lái)確定數(shù)據(jù)在堆中的具體位置。所以堆排序只能對(duì)數(shù)組進(jìn)行排序。