在上一篇博客中，主要是实现各种的排序算法，并针对一些算法进行了优化的处理，下面主要讨论一下非比较排序的算法（计数排序、基数排序），同时并对各种排序算法的性能、时间复杂度、空间复杂度、优缺点、以及适用场景做总结分析。
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)的算法：快速排序、归并排序、堆排序算法，快速排序经过各种的优化算法（三数取中法、区间较小时利用直接插入算法，【上篇博客中详细的介绍了快速排序的优化】）已经相对来说效率提高了很多。
归并排序又称为外排序，外排序其实就是指能够对内存之外（磁盘中）数据进行排序，对于大数据的文件，不能够直接加载到内存中进行排序，我们可以采取将文件划分成小文件，将小的文件加载到内存中进行排序，然后将排好序的数据进行重写，将两个有序的数据文件在重新排序，就能够排好大数据文件。这个读者可以下去进行试验，这里就不做详细的解释。
堆排序的效率虽然还是挺高的，但是堆排序有个致命的缺点，就是只能够对数组进行排序，因为需要通过数组的下标来确定数据在堆中的具体位置。所以堆排序只能对数组进行排序。
原创文章，作者：kepupublish，如若转载，请注明出处：https://blog.ytso.com/194175.html