第2章--数据排序(C++版)

第二章数据排序信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。1.选择排序（1）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（2）排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［38659776492749］第二趟排序后1327［659776493849］第三趟排序后132738[9776496549]第四趟排序后13273849[76976549]第五趟排序后1327384949[976576]第六趟排序后132738494965[9776]第七趟排序后13273849496576[97]最后排序结果1327384949657697例2.1输入n个数，将n个数按从小到大的顺序输出(n=10000)。输入样例:84938659776132749输出样例:1327384949657697归纳上述排序过程，具体实现步骤如下：①读入数据存放在a数组中。②在a[1]～a[n]中选择值最小的元素，与第1位置元素交换，则把最小值元素放入a[1]中。③在a[2]～a[n]中选择值最小的元素，与第2位置元素交换，则把最小值元素放入a[2]中，……④直到第n-1个元素与第n个元素比较排序为止。程序实现方法：用两层循环完成算法，外层循环i控制当前序列最小值存放的数组位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。程序如下：#includeiostreamusingnamespacestd;constintMAXN=10001;intmain(){intn,k,i,j;floattemp,a[MAXN];cinn;for(i=0;in;i++)cina[i];//输入n个数for(i=0;in;i++)//i控制当前序列中最小值存放的数据位置{k=i;for(j=i+1;jn;j++)//在当前无序区a[i..n]中选最小的元素a[k]if(a[j]a[k])k=j;if(k!=i)//交换a[i]和a[k]，将当前最小值放到a[i]位置{temp=a[i];a[i]=a[k];a[k]=temp;}}for(i=0;in;i++)couta[i];return0;}2.冒泡排序冒泡排序的思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。从上述分析中可以看出，每进行一轮的比较之后，n个数的排序规模就转化为n-1个数的排序规模。例如有6个元素需要排序：653412第一趟排序：第二趟排序：第三趟排序：第四趟排序：第五趟排序：五趟结束后，6个整数就已经排序完成。排序过程中，大数慢慢的往后，相当于气泡上升，所以叫冒泡排序。归纳上述排序过程，具体实现步骤如下：①读入数据存放在a数组中。②比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。③对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“冒”到数组第n-1个位置。④n=n-1，如果n不为0就重复前面二步，否则排序完成。程序实现方法：用两层循环完成算法，外层循环i控制每轮要进行多少次的比较，第1轮比较n-1次，第2轮比较n-2次，……，最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否逆序，若逆序就交换这两个元素。【程序实现】#includeiostreamusingnamespacestd;constintMAXN=10001;intmain(){intn,i,j;floattemp,a[MAXN];cinn;for(i=0;in;i++)cina[i];//输入n个数for(i=n-1;i=1;i--)//进行n-1轮冒泡{for(j=0;j=i;j++)//每轮进行i次的比较{if(a[j]a[j+1])//相邻两个元素比较，若逆序就交换swap(a[j],a[j+1]);//交换}}for(i=0;in;i++)//输出排序结果couta[i];return0;}改进的冒泡排序:对于有些数据，我们发现，不一定要n-1次才能排完。例如152346，我们发现只需一趟排序就可以将整个序列排完，于是，我们可以设置一个布尔变量，判断是否有进行交换，如果没有交换，说明已经排序完成，进而减少几趟排序。【程序实现】boolok;for(inti=n-1;i=1;i--){ok=true;//判断是否有交换for(intj=1;j=i;j++){if(a[j]a[j+1]){swap(a[j],a[j+1]);ok=false;}}if(ok==true)break;//没有交换就退出}例2.2车厢重组【问题描述】在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入文件】输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。【输出文件】一个数据，是最少的旋转次数。【输入样例】44321【输出样例】6程序如下：#includeiostream#includecstdiousingnamespacestd;longn,i,j,t,s,a[10000];intmain(){cinn;for(i=1;i=n;i++)cina[i];//输入n个车厢号for(i=1;i=n-1;i++)//冒泡排序另一种写法for(j=1;j=n-i;j++)if(a[j]a[j+1])//判断车厢号是否逆序{swap(a[j],a[j+1]);s++;//统计车厢旋转的次数};couts;//最少的旋转次数return0;}3.插入排序插入排序思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。例如:设n=8，数组a中8个元素是:36,25,48,12,65,43,20,58，执行插入排序程序后，其数据变动情况：第0步:[36]25481265432058第1步:[2536]481265432058第2步:[253648]1265432058第3步:[12253648]65432058第4步:[1225364865]432058第5步:[122536434865]2058第6步:[12202536434865]58第7步:[1220253643485865]程序如下：#includeiostreamusingnamespacestd;constintMAXN=10001;intmain(){intn,i,j,k;floattemp,a[MAXN];cinn;for(i=0;in;i++)cina[i];//输入n个数for(i=0;in;i++){for(j=i-1;j=0;j--)//在前面有序区间中为a[i]找合适的插入位置if(a[j]a[i])break;//找到比a[i]小的位置就退出,插入其后if(j!=i-1){temp=a[i];//将比a[i]大的数据向后移for(k=i-1;kj;k--)a[k+1]=a[k];//将a[i]放在正确位置上a[k+1]=temp;}}for(i=0;in;i++)couta[i];//输出排序的结果return0;}4.桶排序桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。例：输入n个0到100之间的整数，由小到大排序输出。【程序实现】#includeiostream#includecstringusingnamespacestd;intmain()intb[101],n,i,j,k;memset(b,0,sizeof(b));//初始化cinn;for(i=1;i=n;i++){cink;b[k]++;//将等于k的值全部装入第k桶中}for(i=0;i=100;i++)//输出排序结果while(b[i]0)//相同的整数，要重复输出{couti;b[i]--;//输出一个整数后，个数减1}coutendl;}例2.3明明的随机数(Noip2006)【问题描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入文件】输入文件random.in有2行，第1行为1个正整数，表示所生成的随机数的个数：N第2行有N个用空格隔开的正整数，为所产生的随机数。【输出文件】输出文件random.out也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】102040326740208930040015【输出样例】8152032406789300400【分析】本题有一个重要的特点就是每一个数都介于0到1000之间的整数,可以开设一个下标为0～1000的数组b，b[0]记录值为0的个数,b[1]记录值为1的个数，……，b[x]记录值为x的个数，那么从小到大的顺序输出b数组值不为0的b数组下标值。程序如下：#includeiostream#includecstdio#includecstringusingnamespacestd;intmain(){intb[1001],n,i,j,m=0,x;memset(b,0,sizeof(b));//初始化cinn;for(i=1;i=n;i++){cinx;if(b[x]==0)m++;//b[x]为0表示x为新的随机数,m加1b[x]++;//将等于x的值全部装入第x桶中}coutmendl;//不相同的随机数的个数for(i=0;i=1000;i++)//输出排序结果if(b[i]0)couti;coutendl;return0;}5.快速排序快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可