学习目标
1.计数排序
计算机语言发展历史（二）
第二代计算机语言是汇编语言,它采用一定的助记符来代替机器语言中的指令和数据,又称为符号语言。汇编语言一定程度上克服了机器语言难读难改的缺点,同时保持了其编程质量高、所占存储空间少、执行速度快的优点。汇编语言编制的程序(称为源程序)必须经过
汇编程序(一种语言处理程序)翻译成计算机所能识别的机器语言程序(也称为目标程序)后,才能被计算机执行。
计数排序
●邮件分拣,同一个地址的邮件放入这个地址的盒子里,再按地址/顺序投递
●身高排序,身高为150的站一排,151的站一排 … 189的站一排,190的站一排。然后从前到后合成一条队,这样就排好了
●计数排序:统计同一个元素的出现次数,然后根据这些次数进行排序
2.进行计数统计
计数排序的主要步骤如下:
找出待排序数组a中的最大值W,并确定计数数组c的长度,应为W+1。
初始化计数数组c,将每个元素的出现次数初始化为0。
遍历待排序数组a,统计每个元素值i的出现次数,并将其存储在计数数组c[i]中。
遍历计数数组c,找出其中元素值大于0的元素,将其对应的下标输出元素值次。
★计数数组的下标对应待排序的数,计数数组的值对应这个数出现的次数
对o~9的10个整数进行计数排序:
#include<iostream>usingnamespacestd;#defineN10#defineW9待排序数最多数量 N 待排序数中的最大值W 待排序数组 a[]计数数组 c[]这两句是用宏定义来声明两个常量：
- #define N 10：定义 N 为 10，表示待排序数组的最大元素个数，也就是这个程序最多能处理 10 个数字。
- #define W 9：定义 W 为 9，表示待排序数字中的最大值，也就是数组里的元素都不会超过 9。
intmain(){inta[N],c[W+1]={0};//计数数组长度为最大值+1,并且初始值为0intn;cin>>n;输入待排序的数,存放在a数组中。 同时在c数组中计数。 遍历c数组,输出得到有序的数列。return0;}代码
#include<iostream>usingnamespacestd;#defineN10#defineW9intmain(){inta[N],c[W+1]={0};intn;cin>>n;for(inti=0;i<n;i++){/*a[ ]=5 1 1 0 ... c[]=0 2 0 0 0 1... 0 1 2 3 4 5 6 c[1]中值为2,说明1分出现了2次*/cin>>a[i];c[a[i]]++;}//
