《第2章数据排序(C版) (1)》由会员分享，可在线阅读，更多相关《第2章数据排序(C版) (1)（34页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章数据排序数据排序信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。1.选择排序选择排序（1）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（2）排序过程：【示例】：初 始 关键字 49 38 65 97 76 13 27 49第一趟排序后 1338 65 97 76 49 27 49第二趟排序后 13 2765 97 76 49 38 49第三趟排序后 13 2
2、7 38 97 76 49 65 49第四趟排序后 13 27 38 49 76 97 65 49第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38 49 49 65 76 97最后排序结果 13 27 38 49 49 65 76 97例例2.1输入输入n个数，将个数，将n个数按从小到大的顺序输出个数按从小到大的顺序输出(n=10000)。输入样例输入样例:84938659776132749输出样例输出样例:1327384949657697归纳上述排序过程，具体实现步骤如下：读入数据存放在a数
3、组中。在a1an中选择值最小的元素，与第1位置元素交换，则把最小值元素放入a1中。在a2an中选择值最小的元素，与第2位置元素交换，则把最小值元素放入a2中，直到第n-1个元素与第n个元素比较排序为止。程序实现方法：用两层循环完成算法，外层循环i控制当前序列最小值存放的数组位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。程序如下：程序如下：#includeusingnamespacestd;constintMAXN=10001;intmain()intn,k,i,j;floattemp,aMAXN;cinn;for(i=0;iai;/输入n个数for(i=0;in;i+)/i控
4、制当前序列中最小值存放的数据位置k=i;for(j=i+1;jn;j+)/在当前无序区ai.n中选最小的元素akif(ajak)k=j;if(k!=i)/交换ai和ak，将当前最小值放到ai位置temp=ai;ai=ak;ak=temp;for(i=0;in;i+)coutai;return0;2.冒泡排序冒泡排序冒泡排序冒泡排序的思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，直到n-1和n比较，经过一轮比较后，则把最
5、高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。从上述分析中可以看出，每进行一轮的比较之后，n个数的排序规模就转化为n-1个数的排序规模。例如有6个元素需要排序：653412第一趟排序：第二趟排序：第二趟排序：第三趟排序：第三趟排序：第四趟排序：第四趟排序：第五趟排序：第五趟排序：五趟结束后，五趟结束后，6个整数就已经排序完成。排序过程中，大数慢慢的往后，相当于气泡个整数就已经排序完成。排序过程中，大数慢
6、慢的往后，相当于气泡上升，所以叫冒泡排序。上升，所以叫冒泡排序。 归纳上述排序过程，具体实现步骤如下：归纳上述排序过程，具体实现步骤如下： 读入数据存放在读入数据存放在a a数组中。数组中。 比较相邻的前后两个数据，如果前面数据大于后面的数据，比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。就将两个数据交换。 对数组的第对数组的第0 0个数据到个数据到n-1n-1个数据进行一次遍历后，最大的个数据进行一次遍历后，最大的一个数据就一个数据就“冒冒”到数组第到数组第n-1n-1个位置。个位置。 n=n-1n=n-1，如果，如果n n不为不为0 0就重复前面二步，否则排序完成。
7、就重复前面二步，否则排序完成。 程序实现方法：用两层循环完成算法，外层循环程序实现方法：用两层循环完成算法，外层循环i i控制每轮要控制每轮要进行多少次的比较，第进行多少次的比较，第1 1轮比较轮比较n-1n-1次，第次，第2 2轮比较轮比较n-2n-2次，次，最后一轮比较最后一轮比较1 1次。内层循环次。内层循环j j控制每轮控制每轮i i次比较相邻两个元素是否次比较相邻两个元素是否逆序，若逆序就交换这两个元素。逆序，若逆序就交换这两个元素。【程序实现程序实现】#includeusing namespace std;const int MAXN=10001;int main() int n,
8、i,j; float temp,aMAXN; cinn; for (i=0;iai; /输入n个数 for(i=n-1; i=1; i-) /进行n-1轮冒泡 for(j=0; jaj+1) /相邻两个元素比较，若逆序就交换 swap(aj, aj+1); /交换 for (i=0;in;i+) /输出排序结果 coutai=1; i-) ok=true; /ok=true; /判断是否有交换判断是否有交换 for(int j=1; jaj+1) swap(aj,aj+1); ok=false; if(okif(ok=true) break; /=true) break; /没有交换就退出没有
9、交换就退出例例例例2.2 2.2 2.2 2.2 车厢重组车厢重组车厢重组车厢重组【问题描述问题描述问题描述问题描述】 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转如果将桥旋转180180度，则可以把相邻两节车厢的位置交换，用这种度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排
10、列。他退休后，火车站决定将这一工作自动厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。算最少用多少步就能将车厢排序。【输入文件输入文件输入文件输入文件】 输入文件有两行数据，第一行是车厢总数输入文件有两行数据，第一行是车厢总数N N（不大于（不大于1000010000），），第二行是第二行是N N个不同的数表示初始的车厢顺序。个不同的数表示初始的车厢顺序。【输出文件输出文件输出文件输出文件】 一个数据，是最少的旋转次数。一个数据，是最少的旋
11、转次数。【输入样例输入样例输入样例输入样例】 4 4 4 3 2 1 4 3 2 1 【输出样例输出样例输出样例输出样例】 6 6程序如下：程序如下：#include#includeusing namespace std;long n,i,j,t,s,a10000;int main() cinn; for (i=1; iai; /输入n个车厢号 for (i=1; i=n-1; i+) /冒泡排序另一种写法 for (j=1; jaj+1) /判断车厢号是否逆序 swap(aj,aj+1); s+; /统计车厢旋转的次数 ; couts; /最少的旋转次数 return 0; 3.插入排序插入
12、排序插入排序插入排序思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。例如:设n=8，数组a中8个元素是:36,25,48,12,65,43,20,58，执行插入排序程序后，其数据变动情况：第0步:3625481265432058第1步:2536481265432058第2步:25364812654320
13、58第3步:1225364865432058第4步:1225364865432058第5步:1225364348652058第6步:1220253643486558第7步:1220253643485865程序如下：程序如下：#includeusingnamespacestd;constintMAXN=10001;intmain()intn,i,j,k;floattemp,aMAXN;cinn;for(i=0;iai;/输入输入n个数个数for(i=0;i=0;j-)/在前面有序区间中为在前面有序区间中为ai找合适的插入位置找合适的插入位置if(ajj;k-)ak+1=ak;/将将ai放在正确位
14、置上放在正确位置上ak+1=temp;for(i=0;in;i+)coutai;/输出排序的结果输出排序的结果return0;4.桶排序桶排序桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。例：输入例：输入n个个0到到100之间的整数，由小到大排序输出。之间的整数，由小到大排序输出。【程序实现程序实现】#include#includeusingnamespacestd;intmain()intb101,n,i,j,k;memset(b,0,sizeof(b);
15、/初始化cinn;for(i=1;ik;bk+;/将等于k的值全部装入第k桶中for(i=0;i0)/相同的整数，要重复输出couti;bi-;/输出一个整数后，个数减1coutendl;例例2.3 2.3 明明的随机数明明的随机数(Noip2006)(Noip2006)【问题描述问题描述】 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作
16、。【输入文件输入文件】 输入文件random.in 有2行， 第1行为1个正整数，表示所生成的随机数的个数：N 第2行有N个用空格隔开的正整数，为所产生的随机数。【输出文件输出文件】 输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例输入样例】 10 20 40 32 67 40 20 89 300 400 15【输出样例输出样例】 8 15 20 32 40 67 89 300 400【分析分析】 本题有一个重要的特点就是每一个数都介于0到1000之间的整数,可以开设一个下标为01000的数组b，b0记录值为0的个数,b1记录值为1的个数，bx记录值为x的个数，那么从小到大的顺序输出b数组值不为0的b数组下标值。程序如下：程序如下：#include#include#includeusing namespace std;int main() int b1001,n,i,j,m=0,x; memset(b,0,sizeof(b); /初始化 cinn; for (i=1;ix
