这个算法主要用在关键数字(key number)小的时候,按照关键数字排序的效率是非常高的。
比如我们有6个教室的学生需要按教室号排序,如下是学生的信息数据结构:
struct StudentData
{
string name;
int classNum;
StudentData():name("No Name"), classNum(0){}
StudentData(int num, string na):classNum(num), name(na){}
void print();
};
void StudentData::print()
{
cout<<classNum<<"\t\t"<<name<<endl;
}
需要的空间就是关键数字的最大值的空间,比如关键字最大是6,那么就需要6+1个空间。如果是从后面开始填表,那么就只需要6个空间。
思路:
主要需要三个步骤:
1 新建一个关键数字大小+1的vector vi,并以关键字出现的次数为vi的下标,计算其出现的总次数
2 把前面教室号出现的总次数加起来就是本教室号开始填表的位置
3 根据教室号开始填表,每填写一个学生信息,那么就需要把填表下标+1.
三部曲,就只需要三个循环,如C++程序:
class Solution {
public:
void countingSort(vector<StudentData> &vstu)
{
vector<int> vi(MAXCLASS+1);
//三部曲1:计算所有classNum出现的次数
for(auto x:vstu)
{
vi[x.classNum]++;
}
//三部曲2:计算需要摆放数据的初始位置
for (int i = 1; i < vi.size(); i++)
{
vi[i] += vi[i-1];
}
vector<StudentData> tempVstu(vstu.size());
for(auto x:vstu)
{
//三部曲3: x.classNum是student的教室号,前面的教室学生填写完毕,就开始填写这个教室的学生
//所以这个教室号在其他教室学生信息填写完毕之后才填写,所以开始位置是前面学生总和
//x.classNum-1代表前面所有教室号的学生总数,也是本教室号开始填写学生信息的开始号码
//用这个号码在vi中抽去前面填写好的下标
//++代表填了一个学生信息,那么后面填写的学生号需要+1.
tempVstu[vi[x.classNum-1]++] = x;
}
//复制回原来数列
vstu = tempVstu;
}
};
下面是主程序:
int main()
{
vector<StudentData> vstu;
vstu.push_back(StudentData(1,"s1"));
vstu.push_back(StudentData(2,"s2"));
vstu.push_back(StudentData(3,"s3"));
vstu.push_back(StudentData(5,"s5"));
vstu.push_back(StudentData(4,"s4"));
vstu.push_back(StudentData(3,"s33"));
vstu.push_back(StudentData(6,"s6"));
vstu.push_back(StudentData(2,"s22"));
vstu.push_back(StudentData(5,"s55"));
vstu.push_back(StudentData(2,"s222"));
vstu.push_back(StudentData(6,"s66"));
vstu.push_back(StudentData(4,"s44"));
cout<<"Before sort:\nclass number\tstudent name\n";
for (auto x:vstu)
x.print();
cout<<endl;
Solution solu;
solu.countingSort(vstu);
cout<<"After sort:\nclass number\tstudent name\n";
for (auto x:vstu)
x.print();
system("pause");
return 0;
}
运行结果:
分享到:
相关推荐
countingSort 方法实现了计数排序算法。首先,我们遍历一遍原数组,找出其中的最大值,以确定计数数组的大小。然后,创建计数数组 count,并将每个元素的出现次数记录在计数数组中。接下来,根据计数数组中的元素...
麻省理工学院“算法导论”课程中介绍的计数排序算法的实现。 例子 var countingSort = require ( './countingSort.js' ) ; // Construct input [0, 5], therefore an array of size 6 is needed // for the ...
JavaScript计数排序算法计数排序算法计数排序(Counting sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组,数组的下标对应待排序
排序算法 排序算法_基于C语言实现的排序算法之CountingSort实现
经典的排序算法C#源码,包括: 经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序...经典排序算法 - 计数排序Counting sort
CountingSort为AlgorithmMan中的计数排序演示工具(这是可执行文件;需要.net 4.0支持;非源代码)。 原文:C#算法设计排序篇之08-计数排序(附带动画演示程序) 链接:...
伪代码和算法介绍在此:http://www.algorithmist.com/index.php/Counting_sort,本程序是 根据这个伪代码编写的源代码
计数排序并行openmp Esterepositórioabriga实施工具会按顺序对序数进行排序。 Esses algoritmos foram desenvolvidos no Programme da Disciplina deProgramaçãoParalela e Multicore do curso deCiê...
1. 8 Radix sort(基数排序):从最低位开始,每位采用稳定的排序算法(如计数排序)。 1.9 Bucket sort:当输入数据比较均匀时采用。 先将数据区间分为n个桶,把数据分放到对应的桶中;对桶内的数据采用插入排序;...
计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) 广度优先搜索(Breadth-First Search, BFS) 二分查找(Binary Search) 线性查找(Linear ...
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组Count_arr,其中第i个元素是待排序数组Arr中值等于i的元素的个数。然后根据数组Count_arr来将Arr中的元素排到正确的位置。分为四个步骤:1...
java十大排序算法实现 1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) 3. 插入排序(Insertion Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6. 堆排序(Heap Sort) 7. 计数排序...
常见或不常见排序算法的比较! C语言实现. 40M内存10*1024*1024个整数 BoxSort 0.57s CountingSort 0.89s QuickSort 2.52s CombSort 5.03s ShellInsertSort 5.81s MergeSort 6.20s HeapSort 7.66s ...
计数排序(Counting Sort) 循环排序(Cycle Sort) 双重排序(Double Sort) 荷兰国旗排序(Dutch National Flag Sort) 交换排序(Exchange Sort) 外部排序(External Sort) 侏儒排序(Gnome Sort) 堆排序...
def _counting_sort(A, B, k): “””计数排序,伪码如下: COUNTING-SORT(A, B, k) 1 for i ← 0 to k // 初始化存储区的值 2 do C[i] ← 0 3 for j ← 1 to length[A] // 为各值计数 4 do C[A[j]] ← C...
数据结构与算法-Python语言案例实现十大经典排序算法一、 ... 计数排序(Counting Sort)9. 桶排序(Bucket Sort)10. 基数排序(Radix Sort)三、算法总结 十大经典排序算法 一、 引言 授人以鱼不如授人以渔~ 实践是检
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第一章到第八章重要排序等算法的c/c++实现。IDE环境为vc++ 6.0。函数名称与算法导论原文类似。 主要包括: 直接选择排序 归并排序 堆...
将此方法应用于 HEV6580混合动力电动汽车镍氢电池管理系统。系统实现的功能包括: 数据监测、数据显示、CAN 通信、SOC估计、热管理和安全报警。经电池试验台模拟工况试验验证, 电池管理系统各子系统达到设计要求且工 ...
计数排序(Counting sort)是一种根据小整数键对一组对象排序的算法;也就是说,它是一个整数排序算法。它通过计算具有不同键值的对象的数量,并对这些数量使用算术来确定输出序列中每个键值的位置
计数排序计数排序是一种基于特定范围内的键的排序技术。 它通过计算具有不同键值的对象数量来工作(类似于哈希)。