计数排序及其改进 C++代码实现与分析 恋上数据结构笔记

• • 复习梗概
  • 算法思想
  • • 基础思想
    • 改进空间复杂度，改进不能对负数进行排序问题
    • 改进稳定性
  • 计数排序时间空间复杂度
  • 计数排序基础版 代码及输出
  • 计数排序第一次改进版 代码及输出
  • 计数排序终极版 代码及输出（重要）
  • 完整版代码

1. 基础算法思想？
2. 两种改进的思路？重点在于最终版本思想
3. 最终版本是如何做到稳定的？
4. 三个数组（array，counts，temp）彼此间的索引和元素的对应关系？

1. 计数排序适合对在一定范围内的整数进行排序
2. 先找到排序数组的最大值，创建一个最大索引是该最大值的计数数组，初始值全部为0，然后对排序数组进行计数，若元素i出现了一次，就在计数数组的对应i索引处元素+1，全部计数后，只要按照计数数组的索引（原排序数组的元素）和对应的元素（原排序数组元素出现的次数）按顺序输出索引和对应的元素（即输出原元素和其出现的次数）即可
   图片来自网课恋上数据结构与算法，腾讯课堂
   

1. 但是如果按照上述实现，会造成三个问题：1.不是稳定排序 2.及其浪费内存空间，前面0到最小值部分都用不上 3.无法对负整数进行排序，因为计数数组索引只能是正数
2. 初步改进计数排序：同时查找排序数组的最大值和最小值（max and min），开辟空间为max-min+1的容量的数组，此时排序元素与计数数组的索引的对应关系：计数索引+min，即为原排序元素
3. 如下图，为counts数组打印结果，注意索引以及经过+min处理，代表原排序元素
   

4. 即使经过上面的改进依然不能做到稳定的排序，是因为我们按照 计数数组 的索引与次数 输出排序数组，无论如何都做不到稳定，因为两个相同的元素在 计数数组 的索引中是体现不出来区别的。

5. 所以我们从根本上改变了思想，不按照技术数组简单输出，并做出如下改变

6. 依然通过max和min创建计数数组，但计数时，把技术数组的次数变为累加值，即 包括自己在内前面所有元素出现次数的累加和 ；这是，如果累加次数值 为8，就意味着该元素在排序数组中 应该排在第8位

7. 输出数组时，新定义一个和未排序数组大小相同的数组，因为我们一会要用到未排序数组，所以先备份一个

8. 利用未排序数组 和 计数数组，从最右侧向最左侧遍历，遍历到一个元素，先找到其对应在计数数组中的 累加次数值 x（即该元素排序位置），就把其覆盖到备份数组中 x-1的索引处，同时 累加次数值-1（这样若左边还有相同元素，下次就会覆盖到前一个位置，就稳定了）

9. 遍历完成，覆盖完成，排序完成，备份数组覆盖原未排序数组即可。
   图片来自网课恋上数据结构与算法，腾讯课堂

10. 最好最坏平均时间复杂度：O（n+k）其中n为排序数组长度，k为max-min+1（计数数组长度）
11. 空间复杂度O（n+k），来自计数数组和备份数组
12. 因为不是比较排序，所以最好最坏平均时间复杂度都一样
13. 属于空间换时间的典例

比较简单，直接看后面改进版把
void countingSort(vector &array)
{
    int max  = array[0];
    for(int index = 1;index sortedArray;
    for(int index = 0;index <=max;index++){
        for(int i = 0;i 
输入数组：
6 9 6 7 5 8 8 29 15 11 10
计数排序基础版
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
次数 0 0 0 0 0 1 2 1 2 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
算法用时：（微秒）
[AlgoTime: 6001 us]
排序结果：
5 6 6 7 8 8 9 10 11 15 29
 
 
计数排序第一次改进版 代码及输出 
void countingSort2nd(vector &array){
    //遍历排序数组，记录最大值与最小值
    int max = array[0];
    int min = array[0];
    for(int i = 1;iarray[i]){
            min = array[i];
        }
    }

    //创建计数数组，长度为max-min+1，记住创建数组【】里的是长度，不是最大索引
    int *counts = new int[max - min + 1]{0};

    //进行计数，以及计数结果显示
    for(int i = 0;i0)
        {
            array[arrayIndex] = i+min;
            arrayIndex++;
        }
    }
}
 
输入数组：
-6 9 6 7 5 8 8 29 15 11 10
计数排序基础版
索引 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
次数 1 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
算法用时：（微秒）
[AlgoTime: 7003 us]
排序结果：
-6 5 6 7 8 8 9 10 11 15 29
 
 
计数排序终极版 代码及输出（重要） 
void countingSort3rd(vector &array){
    //遍历未排序数组，记录最大最小值
    int min = array[0];
    int max = array[0];
    for(int i = 1; iarray[i]){
            min = array[i];
        }
        if(max =0;index--){
        //array[index]-min = counts数组对应元素索引
        //counts[数组对应元素索引] = 数组对应元素在排序序列中的位置
        //counts[数组对应元素索引] - 1 = 数组对应元素在排序数组中的索引
        temp[counts[array[index]-min]-1] = array[index];
        counts[array[index]-min]--;
    }
    
    //用备份数组覆盖原数组
    for (int i = 0; i < array.size(); i++)
    {
        array[i]=temp[i];
    }
}
 
输入数组：
-6 9 6 7 5 8 8 29 15 11 10
计数排序终极版
索引 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
累加次数 1 0 0 0 0 0 0 0 0 0 0 2 3 4 6 7 8 9 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 11
算法用时：（微秒）
[AlgoTime: 6000 us]
排序结果：
-6 5 6 7 8 8 9 10 11 15 29 
 
 
完整版代码 
#include 
#include 
#include "MeasureAlgoTime.hpp"
using namespace std;

void vectorPrint(vector &array)
{
    for (int i = 0; i < array.size(); i++)
    {
        cout << array[i] << ' ';
    }
    cout << endl;
}

void arrayPrint(int array[],int length){
    cout<<"次数"<<" ";
    for(int i = 0;i &array)
{
    int max  = array[0];
    for(int index = 1;index sortedArray;
    for(int index = 0;index <=max;index++){
        for(int i = 0;i &array){
    //遍历排序数组，记录最大值与最小值
    int max = array[0];
    int min = array[0];
    for(int i = 1;iarray[i]){
            min = array[i];
        }
    }

    //创建计数数组，长度为max-min+1，记住创建数组【】里的是长度，不是最大索引
    int *counts = new int[max - min + 1]{0};

    //进行计数，以及计数结果显示
    for(int i = 0;i0)
        {
            array[arrayIndex] = i+min;
            arrayIndex++;
        }
    }
}

void countingSort3rd(vector &array){
    //遍历未排序数组，记录最大最小值
    int min = array[0];
    int max = array[0];
    for(int i = 1; iarray[i]){
            min = array[i];
        }
        if(max =0;index--){
        //array[index]-min = counts数组对应元素索引
        //counts[数组对应元素索引] = 数组对应元素在排序序列中的位置
        //counts[数组对应元素索引] - 1 = 数组对应元素在排序数组中的索引
        temp[counts[array[index]-min]-1] = array[index];
        counts[array[index]-min]--;
    }
    
    //用备份数组覆盖原数组
    for (int i = 0; i < array.size(); i++)
    {
        array[i]=temp[i];
    }
}


int main()
{
    Tools::Time::AlgoTimeUs time1;
    Tools::Time::AlgoTimeUs time2;
    Tools::Time::AlgoTimeUs time3;

    vector array;
    array = {6, 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};
    vector array2 = {-6, 9, 6, 7, 5, 8, 8, 29, 15, 11, 10};
    vector array3 = array2;

    cout<<"输入数组："<