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

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

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

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

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