学习目标

1.计数排序

计算机语言发展历史（二）

第二代计算机语言是汇编语言,它采用一定的助记符来代替机器语言中的指令和数据,又称为符号语言。汇编语言一定程度上克服了机器语言难读难改的缺点,同时保持了其编程质量高、所占存储空间少、执行速度快的优点。汇编语言编制的程序(称为源程序)必须经过
汇编程序(一种语言处理程序)翻译成计算机所能识别的机器语言程序(也称为目标程序)后,才能被计算机执行。

计数排序

●邮件分拣,同一个地址的邮件放入这个地址的盒子里,再按地址/顺序投递
●身高排序,身高为150的站一排,151的站一排 … 189的站一排,190的站一排。然后从前到后合成一条队,这样就排好了
●计数排序:统计同一个元素的出现次数,然后根据这些次数进行排序

2.进行计数统计

计数排序的主要步骤如下:

1. 找出待排序数组a中的最大值W,并确定计数数组c的长度,应为W+1。

2. 初始化计数数组c,将每个元素的出现次数初始化为0。

3. 遍历待排序数组a,统计每个元素值i的出现次数,并将其存储在计数数组c[i]中。

4. 遍历计数数组c,找出其中元素值大于0的元素,将其对应的下标输出元素值次。

★计数数组的下标对应待排序的数,计数数组的值对应这个数出现的次数

对o~9的10个整数进行计数排序:

#include<iostream>
using namespace std;
#define N 10
#define W 9
待排序数最多数量 N
待排序数中的最大值W
待排序数组 a[]
计数数组 c[]

这两句是用宏定义来声明两个常量：

1. #define N 10：定义 N 为 10，表示待排序数组的最大元素个数，也就是这个程序最多能处理 10 个数字。
2. #define W 9：定义 W 为 9，表示待排序数字中的最大值，也就是数组里的元素都不会超过 9。

int main() {
	int a[N], c[W+1]={0};//计数数组长度为最大值+1,并且初始值为0
	int n;
	cin>>n;
	输入待排序的数,存放在a数组中。
	同时在c数组中计数。
	
	遍历c数组,输出得到有序的数列。
	
	return 0;
}

代码

#include<iostream>
using namespace std;
#define N 10
#define W 9

int main() {
	int a[N], c[W+1]={0};
	int n;
	cin>>n;
	for(int i=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] ]++;
	}
	
	//遍历c数组,输出得到有序的数列。
//	输出谁?输出几次?	
	for(int i=0;i <= W;i++) {
		for(int j=0;j<c[i];j++) {
			cout << i << " ";//分数i要输出c[i]次
		}
	}
	return 0;
}

完整代码

#include<iostream>
using namespace std;
#define N 10
#define W 9

int main() {
	int a[N], c[W+1]={0};
	int n;
	cin>>n;
	
	for(int i=0;i<n; i++) {
		cin>>a[i];
		c[a [i]]++;
	}
	
	for(int_i=0;i <= W; i++) {
		for(int j=0;j<c[i] ;j++) {
			cout << i << " ";//i输出c[i]次
		}
	}
	return 0;
}

排序前:5 1 1 9 1 6 2 8 3 8
排序后:1 1 1 2 3 5 6 8 8 9
· 时间复杂度为O(n)
· 需要额外的空间来存储计数数组,数组长度与参与排序的最大值W有关
· 是不稳定的排序(本实现方式而 言)

计数排序-去重复

#include<iostream>
using namespace std;
#define N 10
#define W 9

int main() {
	int a [N], c[W+1]={0};
	int n;
	cin>>n;
	for(int i=0;i<n; i++) {
		cin>>a[i];
		c[a [i]]++;
	}
	for(int i=0;i <= W;i++) {
		if (c[i]>0)
			cout << i << " ";//i输出1次
	}
	return 0;
}		

计数排序还可以去重复数
排序前:5 1 1 9 1 6 2 8 3 8
排序后:1 2 3 5 6 8 9
只需要改动一下输出部分:
c[i]>0时,i输出一次即可,无需输出c[i]次!

计数排序-总结

● 计数排序没有进行元素间比大小,所以是一种非比较排序算法
● 需要额外的空间来存储计数数组
● 时间复杂度和空间复杂度是O(n+w)(其中w是整数的范围),当w是常量时,时间和空间复杂度是O(n)
●一般情况下,都快于任何比较排序算法。极端情况下,当整数范围过大时可能不如快速排序
一般用于一定范围内的非负整数排序
· 不适用于浮点数排序
· 需要一些额外的处理后,可以对负整数进行排序

明明的随机数

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了
N个1到1000之间的随机整数(N <= 100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入】有2行。第1行为1个正整数N,表示所生成的随机数的个数。第2行有N个用空格隔
开的正整数,为所产生的随机数。
【输出】2行。第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开
的正整数,为从小到大排好序的不相同的随机数。
【输入样例】

10

20 40 32 67 40 20 89 300 400 15

【输出样例】

15 20 32 40 67 89 300 400
每一个数都是介于0到1000之间的整数,优选计数排序法!

计数数组长度?1000+1

int c[1001] = {0};

计数后如何去掉重复的数?
c[i]>0时,下标i输出一次即可!
比如计数后c[20]的值是2,表示20出现2次,只需要输出一次20。

#include<bits/stdc++.h>
using namespace std;
#define Max 1000
int main()
{
	int c[Max+1]={0};
	int n,x,m=0;
	cin>>n;
	//输入n个待排序的数，对于输入x,相应的 c[x]++
	for(int i=1;i<=n;i++) {
		cin>>x;
		c[x]++;//x值出现次数加1 
	}
	//遍历c，统计元素值>0的元素个数m,并输出
	for(int i=0;i<=Max;i++) 
		if(c[i]>0)
			m++;
	cout<<m<<endl;
	//遍历c,输出元素值>0的元素下标（1次）
	for(int i=0;i<=Max;i++) 
		if(c[i]>0)
			cout<<i<<" ";
	return 0;
}

【注意】

· 不要忘记,计数数组c的所有元素的初始值必须为o
· 同样,m也要初始化为0
【思考】这个代码的时间复杂度?
O(n)

正负数排序

输入n(n <= 100)和n个整数(每个数的范围是-100~100),从小到大排序后输出。
【输入】两行。第一行是数字n,第二行是n个整数。
【输出】排序后的结果,两个数之间用空格隔开。
【输入样例】
5
-5 -4 3 -2 -1

【输出样例】
-5 -4 -2 -1 3
计数排序一般只能处理非负整数
(需要用待排序数作为数组下标,而数组下标必须是非负整数)
参与排序的整数有正有负
还可以用计数排序法吗?

思路

负数排序输出的注意点:

1. -100 <- 1,所以需要逆序遍历neg[],得到从小到大的排序的所有负数
2. 输出负数需要在下标数字前添加’-’

#include<bits/stdc++.h>
using namespace std;
#define Max 100
int main()
{
	int poi[Max+1]={0};//非负数计数数组
	int neg[Max+1]={0};//负数计数数组
	int n,temp;
	cin>>n;
	//输出n个数，并根据正负数分别计数
	for(int i=1;i<=n;i++) {
		cin>>temp;
		if(temp>0){
			poi[temp]++;
		}else{
			neg[-temp]++;
		}
	}
	//按顺序遍历负数计数数组，输出所有负数
	for(int i=Max;i>=1;i--){
		for(int j=0;j<neg[i];j++)
			cout<<"-"<<i<<" ";
	}
	//按顺序遍历正数计数数组，输出所有非负数
	for(int i=0;i<Max;i++) {//顺序遍历pos[],i输出pos[i]次
		for(int j=0;j<poi[i];j++) 
			cout<<i<<" ";
	}
	 
	return 0;
}

【注意】
· 非负整数和负整数分别计数
· 负数作为下标时,要先转成正数
· 同样输出时,负数需要在数字前添加’-’
· 负数的计数数组需要反向遍历才能得到从小到大排序的结果

本次课程的知识点

1. 计数排序的原理和方法
2. 计数排序的算法特性
3. 计数排序练习:明明的随机数、正负数排序
   
   

分发试卷

【编程挑战】某次月考结束后,小六班数学老师批改完试卷,准备下节课分发讲评试卷。老师想要按照从高到低的方式分发试卷,你能够帮助老师重新整理这些试卷,按照从高到低的方式输出这些成绩。
【输入】两行,第一行为一个正整数n,表示小六班参加此次月考的学生人数(0<n<50)。第二行n个正整数,代表小六班参加此次月考的每一个学生的成绩,成绩均在0-100之间(包含0与100)。
【输出】一行,按照从高到低输出每位学生成绩。
【输入用例】
10
100 98 97 98 88 90 76 100 93 92
【输出用例】100 100 98 98 97 93 92 90 88 76

#include<iostream>
using namespace std;
int main() {
	int x, c[101]={0};
	int n;
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>x;
		c [x] ++;
	}
	for(int i=100;i>=0;i -- ){
		for(int j=0;j<c[i] ;j++) {
			cout << i << " ";
		}
	}
	return 0;
}

【注意】对计数数组逆序遍历才能得到从高到低的排序结果。