计数排序算法——C++

计数排序算法——C++

计数排序是时间复杂度为 O(n + m)的算法，空间复杂度为O(n + m)；算法思想跟散列表哈希hash有些类似，主要是利用一段有序数组计算对应元素的下表个数，然后依次输出有数组元素进行排列。基本计数排序是不稳定算法，但是优化后计数排序是稳定算法。本文主要讲解基本计数排序和优化后计数排序。

使用条件：数组必须是整数或者能全部映射为整数，数组所有元素必须在有限较集中范围；

一、具体实现步骤

1.计算原始数组的最大值max和最小值min范围，然后创建一个长度为max--min+1的排序数组sortArr(max--min+1)；

该数组sortArr目的是计算每个原始数组每个元素的个数

auto minmax = std::minmax_element(nums.begin(), nums.end()); // minmax_element(begin，end)可以输入迭代器而minmax(l,r)不能输入迭代器
int min = *minmax.first;
int max = *minmax.second;
int index = 0;
vector sortArr(max - min + 1, 0); // 创建一段数组用来存储每个元素个数
vector result(nums.size()); // 创建一段数组用来存储每个元素个数

2.遍历原始数组，将原始数组的值作为排序数组sortArr的下标进行计数；

此时原始数组所有元素个数已经计算出来并顺序存放；注意：存储下标的时候需要减去最小值，将原始数组缩放到排序数组范围内。

for (const auto& it : nums) // 遍历原始数组，计算所有元素个数；sortArr下标是元素，值是该元素个数
{
    sortArr[it - min]++;
}

3.遍历排序数组sortArr，将所有非零的值取出下标作为输出数组元素；

这里注意取出下标的时候需要加上最小值，因为前面存入的时候减了最小值。

for (int i = 0; i < sortArr.size(); ++i) // 遍历有序数组，值为非零则取出排列
{
    while (sortArr[i])
    {
        result[index] = i + min;
        ++index;
        --sortArr[i];
    }
}

4.最后返回结果数组或者赋值给原来数组

nums = result;

 二、完整代码示例

Sorts.h

#pragma once

#include 
#include 

using namespace std;

struct Sorts {    
    void count(vector& nums);    
    void print(vector& nums);
};

Sorts.cpp

#include "Sorts.h"
#include 

void Sorts::count(vector& nums)
{
    if (nums.size() <= 1)
        return;
    auto minmax = std::minmax_element(nums.begin(), nums.end()); // minmax_element(begin，end)可以输入迭代器而minmax(l,r)不能输入迭代器
    int min = *minmax.first;
    int max = *minmax.second;
    int index = 0;
    vector sortArr(max - min + 1, 0); // 创建一段数组用来存储每个元素个数
    vector result(nums.size()); // 创建一段数组用来存储每个元素个数
    for (const auto& it : nums) // 遍历原始数组，计算所有元素个数；sortArr下标是元素，值是该元素个数
    {
        sortArr[it - min]++;
    }
    for (int i = 0; i < sortArr.size(); ++i) // 遍历有序数组，值为非零则取出排列
    {
        while (sortArr[i])
        {
            result[index] = i + min;
            ++index;
            --sortArr[i];
        }
    }
    nums = result;
}

void Sorts::print(vector& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

main.cpp

 #include 
#include "Sorts.h"

using namespace std;

int main()
{
    vector nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.count(nums);
    sorts.print(nums);
   
	return 1;
}

输出结果：

三、优化版计数排序

正常版本的计数排序虽然时间复杂度很快，但是却不是绝对的，假如数据量很多，效率不一定比快速排序算法高，当有几个相同元素时，会改变原来元素相对位置，是不稳定排序，因此需要优化。

3.1 优化的思路

主要是将排序数组sortArr里非零元素作为权值依次加入到后面元素里。具体示例如下所示：

第333次变化后的排序数组sortArr的值即是输出有序数组的下标，索引即是缩放后的元素。代码实现如下：

for (auto& it : sortArr) // 遍历排序数组，将前面非零元素依次累加到后面
{
    if (it)
        tmp += it; // 非零则累加
    it = tmp; // 变化后元素
}
// 经过上面的变化，此时排序数组sortArr的元素即为初始数组元素排序后的位置

那么问题来了，该如何还原排序后元素呢？

答案很简单，因为变化后排序数组sortArr的值是原始数组nums元素排序后索引下标，所以只需要依次遍历原始数组nums，然后找打对应下标，将该原始数组的元素依次取出排列到有序数组即可，代码实现如下：

for (int i = nums.size(); i > 0; --i) // 逆序遍历原始数组，找到对应位置输出有序数组
{
    int index = sortArr[nums[i - 1]] - 1; // 找到元素nums[i-1]排序后位置索引；sortArr[ nums[i-1] ]的值表示元素nums[i-1]在有序数组中排第几个位置
    result[index] = nums[i - 1];
    sortArr[nums[i - 1]]--; // 排序数组取出一个元素排列后，该元素的值需要减一，即如果下次还命中该相同元素，则往后一位排列
}
nums = result;

3.2 优化计数排序跟基本计数排序主要区别 3.2.1变化后的排序数组sortArr存储的元素值不同

基本计数排序的排序数组sortArr存储的是初始化数组nums每个元素个数，而优化后计数排序sortArr的元素存储的是初始化数组nums排序后的位置（即排序后在第几位）

3.2.2遍历排序数组sortArr取元素方式不一样

基本计数排序主要是依次遍历排序数组sortArr，当其值非零时取元素并且该值减一，而优化计数排序主要是逆向遍历原始数组nums，通过在排序数组sortArr中找到原始数组nums每个元素的下标，而赋值给结果数组result

基本计数排序主要区别：

for (int i = 0; i < sortArr.size(); ++i) // 遍历有序数组，值为非零则取出排列
{
    while (sortArr[i])
    {
        result[index] = i + min;
        ++index;
        --sortArr[i];
    }
}
nums = result;

优化计数排序主要区别：

for (auto& it : sortArr) // 遍历排序数组，将前面非零元素依次累加到后面
{
    if (it)
        tmp += it; // 非零则累加
    it = tmp; // 变化后元素
}
// 经过上面的变化，此时排序数组sortArr的元素即为初始数组元素排序后的位置

for (int i = nums.size(); i > 0; --i) // 逆序遍历原始数组，找到对应位置输出有序数组
{
    int index = sortArr[nums[i - 1]] - 1; // 找到元素nums[i-1]排序后位置索引；sortArr[ nums[i-1] ]的值表示元素nums[i-1]在有序数组中排第几个位置
    result[index] = nums[i - 1];
    sortArr[nums[i - 1]]--; // 排序数组取出一个元素排列后，该元素的值需要减一，即如果下次还命中该相同元素，则往后一位排列
}
nums = result;

 四、优化计数排序完整代码示例

Sorts.h

#pragma once

#include 
#include 

using namespace std;

struct Sorts {    
    void count1(vector& nums);    
    void print(vector& nums);
};

Sorts.cpp

#include "Sorts.h"
#include 

void Sorts::count1(vector& nums)
{
    if (nums.size() <= 1)
        return;
    auto minmax = std::minmax_element(nums.begin(), nums.end()); // minmax_element(begin，end)可以输入迭代器而minmax(l,r)不能输入迭代器
    int min = *minmax.first;
    int max = *minmax.second;    
    int tmp = 0;
    vector sortArr(max - min + 1, 0); // 创建一段数组用来存储每个元素个数
    vector result(nums.size()); // 创建一段数组用来存储每个元素个数
    for (const auto& it : nums) // 遍历原始数组，计算所有元素个数；sortArr下标是元素，值是该元素个数
    {
        sortArr[it - min]++;
    }
    for (auto& it : sortArr) // 遍历排序数组，将前面非零元素依次累加到后面
    {
        if (it)
            tmp += it; // 非零则累加
        it = tmp; // 变化后元素
    }
    // 经过上面的变化，此时排序数组sortArr的元素即为初始数组元素排序后的位置

    for (int i = nums.size(); i > 0; --i) // 逆序遍历原始数组，找到对应位置输出有序数组
    {
        int index = sortArr[ nums[i-1] ] - 1; // 找到元素nums[i-1]排序后位置索引；sortArr[ nums[i-1] ]的值表示元素nums[i-1]在有序数组中排第几个位置
        result[index] = nums[i - 1];
        sortArr[nums[i - 1]]--; // 排序数组取出一个元素排列后，该元素的值需要减一，即如果下次还命中该相同元素，则往后一位排列
    }
    nums = result;
}

void Sorts::print(vector& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

main.cpp

 #include 
#include "Sorts.h"

using namespace std;

int main()
{
    vector nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.count1(nums);
    sorts.print(nums);
   
	return 1;
}

输出结果：