程序分享--排序算法--计数排序

关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》《做好面试准备，迎接2024金三银四》。

-------------------------------------正文----------------------------------------

计数排序：概述
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序：算法描述
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组count的第i-min项；
根据计数值对数组进行填充。

#include 
#include 
#include 
 
void countingSort(const std::vector<int>& input, std::vector<int>& output, int max) {
    std::vector<int> count(max + 1, 0);
    
    // Calculate count of each element
    for (int i : input)
        count[i]++;
 
    // Calculate start index for each element
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];
 
    // Sort the elements
    for (int i = input.size() - 1; i >= 0; i--) 
    {
        output[count[input[i]] - 1] = input[i];
        count[input[i]]--;
    }
}
 
int main() 
{
    std::vector<int> vec = { 4，8，9，2，100，400，20，7，17，31，22，0，1，55，30 };
	cout << "排序前：";
	for (int i = 0; i < 15; i++)
		cout << vec[i] << ' ';
	cout << std::endl;
 
    int max = *std::max_element(vec.begin(), vec.end());
    std::vector<int> sorted(data.size());
	countingSort(vec, sorted, max);
 
	cout << "排序后：";
	for (int i = 0; i < 15; i++)
		cout << sorted[i] << ' ';
	cout << std::endl;
 
    return 0;
}