四、计数排序

1.基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

       1. 统计相同元素出现次数；

       2. 根据统计的结果将序列回收到原来的序列中；

注意：

如果是这样的数组进行计数排序，按照上图所说这里count数组空间就开辟1501个空间，但是这个待排序数组只有7个元素，那么前面的1000个空间就浪费了，为了解决这样的问题，在开辟空间上可以采用：最大值-最小值+1的方式进行空间开辟（1500-1000+1=501）；

2.动图演示

3.代码实现

//计数排序
void CountSort(int* a, int n)
{
  int max = a[0], min = a[0];
    //找出最大值和最小值
  for (int i = 1; i < n; i++)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  int range = max - min + 1;
  int* count = (int*)malloc(sizeof(int) * range);
  memset(count, 0, sizeof(int) * range);//将count数组元素全部置为0
  if (count == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  //统计次数
  for (int i = 0; i < n; ++i)
  {
    count[a[i] - min]++;
  }
  //根据次数，进行排序
  int j = 0;
  for (int i = 0; i < range; ++i)
  {
    while (count[i]--)
    {
      a[j++] = i + min;
    }
  }
}

五、排序算法总结

1.时间及空间复杂度

2.排序算法的稳定性

稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[ i ] = r[ j ]，且r[ i ]在r[ j ]之前，而在排序后的序列中，r[ i ]仍在r[ j ]之前，则称这种排序算法是稳定的；否则称为不稳定的。

1.稳定的排序

冒泡排序、直接插入排序、归并排序；

2.不稳的排序

选择排序、希尔排序、堆排序、快排、计数排序；