2020-2021学年信息学奥赛资料 第十三课 一维数组排序及综合应用（适用于高中）课件（23张PPT）

第十三课 一组数组排序及综合应用

目 标
01、学会一维数组的元素排序。
02、 运用一维数组解决实际问题
一维数组的元素排序
“排序”就是按照某个关键字的大小，将若干对象从小到大或者从大到小进行重新排列。关键字是对象的某一个属性，它可以是任何基本数据类型，甚至结构体等。
例如，体育课上我们会按照身高从矮到高站队，这就是“升序”排序，身高是我们每个人的一个属性，也就是排序的关键字。再如，将所有单词按照“字典序”倒过来排序，如zoo,yes,most,key,computer,book,bad,apple等，就是“降序”排序，关键字的类型就是字符串。
排序算法非常多，其中最基本的有选择排序、冒泡排序和插入排序三种。其本质上都是通过数组中的元素比较和交换来实现的，关键是数组下标的分析。
例1、站队
【问题描述】
给出 n 个同学的身高，请根据他们的身高升序排列并输出排序结果。
【输入格式】
第一行 1 个正整数 n，表示有 n 个同学的身高，2第二行包含 n 个正整数，之间用一个空格隔开，表示 n 个同学的身高。每个同学的身高都在 150~200 厘米之间。
【输出格式】
一行 n 个正整数，之间用一个空格隔开，表示 n 个同学根据身高升序排列的结果。
【输入样例】
7
180 170 176 160 155 150 160
【输出样例】
150 155 160 160 170 176 180
【问题分析】
算法1、选择排序
选择排序的基本思想是：每一趟从待排序的数据中，通过“打擂台”比较选出最小元素，放在这些数据的最前面。这样，第一趟把 n 个数中（第 1 个到第 n 个）最小的放在第一个位置，第二趟把剩余的 n-1 个数中（第 2 个到第 n 个）最小的放在第二个位置，第三趟把剩余的 n-2 个数中（第 3 个到第 n 个）最小的放在第三个位，……第 n-1 趟把剩下的 2 个数中（第 n-1 个到第 n 个）最小的放在第 n-1 个位置，剩下的最后一个数（第 n 个）一定最大，自然落在了第 n个位置。
选择排序
#include
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i <= n; i++){
k = i;
for(j = i+1; j <= n; j++)
if(h[j] < h[k]) k = j;// 在 i~n 之间的最小元素
temp = h[i];
h[i] = h[k];
h[k] = temp;// 将 i~n 之间的最小元素放到第 i 个位置
}
for(i = 1; i < n; i++) cout << h[i] << “ “ ;
cout << h[n] << endl;
return 0;
}
算法2、冒泡排序
冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果“逆序”就交换。这样，一趟排序结束后，最大的元素就放在了第 n 个位置了。对于样例数据，第一趟冒泡排序的过程如下：
用同样的方法，第二趟把剩余的前 n-1 个数中最大的交换到第 n-1 个位置，第三趟把剩余的前 n-2 个数中最大的交换到第 n-2 个位置，……经过 n-1 趟，排序结束。
冒泡排序
#include
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++)
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << “ “ ;
cout << h[n] << endl;
return 0;
}
对于冒泡排序，我们还可以做些算法“优化”。如果一趟排序下来，都没有任何“逆序”数对，即没有发生“交换”操作，则说明已经排好序了。此时，就可以立刻退出循环。
优化后的冒泡排序
#include
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++){
bool flag = true;
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
flag = false;
}
if(flag) break;
}
for(i = 1; i < n; i++) cout << h[i] << “ “ ;
cout << h[n] << endl;
return 0;
}
算法3、插入排序
插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；第二趟，把第 3 个数插入进去，保证前 3 个数有；……第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。
插入排序
#include
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 2; i <= n; i++){
temp = h[i];
k = 1;
while(h[k] <= temp && k < i) k++;
for(j = i-1; j >= k; j--) h[j+1] = h[j];
h[k] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << “ “ ;
cout << h[n] << endl;
return 0;
}
一组数组综合应用

例1、学习对象
【问题描述】
n 个信息学选手站在一排，每个选手的位置依次用 1~n 表示，第 i 个信息学选手的编程能力用一个整数 H i 表示。每个信息学选手都希望找一个编程能力比自己高但又与自己编程能力最接近的选手学习，如果有多个符合条件的选手则选择位置在最前面的选手学习。请编程输出每位选手学习对象的位置，如果没有学习对象，则输出 0。
【输入格式】
第 1 行一个正整数 n，1≤n≤1000；
第 2~n+1 行共 n 个正整数，依次表示每位选手的编程能力，1≤H i ≤1000000。
【输出格式】
n 行，每行输出一个整数表示每个选手学习对象的位置。
【输入样例】
6
3
2
6
1
1
2
【输出样例】
3
1
0
2
2
1
【问题分析】
第i个选手的学习对象就是从前往后查找一个选手j，要求Hi//p5-6-1
#include
using namespace std;
int n,i,j,ans,maxh,h[1001];
int main(){
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i <= n; i++){
ans = 0; maxh = 1000001;
for(j = 1; j <= n; j++)
if(h[j] > h[i] && h[j] < maxh){
ans = j; maxh = h[j];
}
cout << ans << endl;
}
return 0;
}
例2、商品排序
【问题描述】
某商场的仓库中有 n 件商品，每件商品的价格在 0~1000 之间（价格为 0 的商品为赠品）。
现在商场经理要求将这 n 件商品按价格由低到高排序。请编程输出 n 件商品排序后的情况。
【输入格式】
第一行一个正整数 n，表示有 n 件商品，1≤n≤100000。
接下来的 n 行，每行一个整数，表示第 i 件商品的价格。
【输出格式】
n 行，每行输出一个整数。
【输入样例】
5
1
8
1
2
2
【输出样例】
1
1
2
2
8
【问题分析】
本题可以选用学过的任意一种排序算法实现，但是测试程序发现会“超时”，因为本题最多有 100000 件商品，三种排序都需要两层循环嵌套。
其实，分析数据发现一个重要特征：数据虽然很多，但是数据范围比较小。这种情况下，可以使用另外一种排序算法——桶排序。定义一个 int 型数组 num[1001]，num[x]记录整数 x 出现的次数，初始化都为 0，每读到一个数 x，就执行 num[x] = num[x]+1。输出时，从 0 ~ 1000 穷举 x，每个 x 输出 num[x]次。
桶排序
#include
using namespace std;
int n,i,j,number,num[1001];
int main(){
cin >> n;
for(i = 1; i <= n; i++){
cin >> number;
num[number]++;// 记录整数 number 出现的次数
}
for(i = 0; i < 1001; i++)
for(j = 1; j <= num[i]; j++)
cout << i < return 0;}
例3、素数大酬宾
【问题描述】
某商场的仓库中有 n 种商品，每件商品按 1~n 依次编号。现在商场经理突发奇想，决定将编号为素数（质数）的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理员将编号为素数的商品选出来。
【输入格式】
一行一个正整数 n，表示有 n 种商品，2≤n≤100000。
【输出格式】
一行若干个正整数，表示若干种商品编号且每个编号均为素数，请从小到大输出，每两个数之间有一个空格。
【输入样例】
20
【输出样例】
2 3 5 7 11 13 17 19
【问题分析】
算法1、穷举法
穷举商品编号 2~n，判断每个编号是否为素数。这种方法效率不高，一旦 n 过大，程序就会超时。

#include
#include
using namespace std;
int main(){
int n,i,j; bool flag;
cin >> n;
cout << 2;
for(i = 3; i <= n; i++){
flag = true;
for(j = 2; j <= sqrt(i); j++)
if(i % j == 0){flag = false;break;}
if(flag) cout << “ “ << i;
}
cout << endl;
return 0;
}