Blame: Algorithm/CountSort.cpp - huihut/interview

huihut / interview UNCLAIMED

📚 C/C++ 技术面试基础知识总结，包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。This repository is a summary of the basic knowledge of recruiting job seekers and beginners in the direction of C/C++ technology, including language, program library, data structure, algorithm, system, network, link loading library, interview experience, recruitment, recommendation, etc.

0 0 10 C++

Normal View History Raw

-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+								/*****************
-												修改排序算法代码

											
										
										
											2018-04-16 13:38:05 +08:00
+								计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+								计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
 								如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
 								计数排序不是比较排序，排序的速度快于任何比较排序算法。
 								时间复杂度为 O（n+k），空间复杂度为 O（n+k）
 								算法的步骤如下：
 . 找出待排序的数组中最大和最小的元素
 . 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
 . 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
 . 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
 								*****************/
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+								#include <iostream>
 								#include <vector>
 								#include <algorithm>
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
 								using namespace std;
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+								// 计数排序
 								void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+								{
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+									// 确保待排序容器非空
 									if (vecRaw.size() == 0)
 										return;
 									// 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
 									int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
-												计数排序中计数容器重命名为 vecCount

											
										
										
											2018-11-06 22:13:00 +08:00
+									vector<int> vecCount(vecCountLength, 0);
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
 									// 统计每个键值出现的次数
 									for (int i = 0; i < vecRaw.size(); i++)
-												计数排序中计数容器重命名为 vecCount

											
										
										
											2018-11-06 22:13:00 +08:00
+										vecCount[vecRaw[i]]++;
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
 									// 后面的键值出现的位置为前面所有键值出现的次数之和
 									for (int i = 1; i < vecCountLength; i++)
-												计数排序中计数容器重命名为 vecCount

											
										
										
											2018-11-06 22:13:00 +08:00
+										vecCount[i] += vecCount[i - 1];
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
 									// 将键值放到目标位置
 									for (int i = vecRaw.size(); i > 0; i--)	// 此处逆序是为了保持相同键值的稳定性
-												计数排序中计数容器重命名为 vecCount

											
										
										
											2018-11-06 22:13:00 +08:00
+										vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+								}
 								int main()
 								{
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+									vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
 									vector<int> vecObj(vecRaw.size(), 0);
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+									CountSort(vecRaw, vecObj);
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
-												修复计数排序的异常，让原始序列的最大值+1作为计数容器的大小；解决算法目录与STL算法目录的链接冲突问题

											
										
										
											2018-11-06 21:58:47 +08:00
+									for (int i = 0; i < vecObj.size(); ++i)
 										cout << vecObj[i] << "  ";
 									cout << endl;
-												计数排序中计数容器重命名为 vecCount

											
										
										
											2018-11-06 22:13:00 +08:00
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+									return 0;
 								}