数据结构—各类‘排序算法’实现（下）

       在上一篇博客中，主要是实现各种的排序算法，并针对一些算法进行了优化的处理，下面主要讨论一下非比较排序的算法（计数排序、基数排序），同时并对各种排序算法的性能、时间复杂度、空间复杂度、优缺点、以及适用场景做总结分析。

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)的算法：快速排序、归并排序、堆排序算法，快速排序经过各种的优化算法（三数取中法、区间较小时利用直接插入算法，【上篇博客中详细的介绍了快速排序的优化】）已经相对来说效率提高了很多。

       归并排序又称为外排序，外排序其实就是指能够对内存之外（磁盘中）数据进行排序，对于大数据的文件，不能够直接加载到内存中进行排序，我们可以采取将文件划分成小文件，将小的文件加载到内存中进行排序，然后将排好序的数据进行重写，将两个有序的数据文件在重新排序，就能够排好大数据文件。这个读者可以下去进行试验，这里就不做详细的解释。

       堆排序的效率虽然还是挺高的，但是堆排序有个致命的缺点，就是只能够对数组进行排序，因为需要通过数组的下标来确定数据在堆中的具体位置。所以堆排序只能对数组进行排序。