第2章--数据排序(C++版)ppt课件.ppt

《第2章--数据排序(C++版)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章数据排序信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。1.选择排序（1）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（2）排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［38659776492749］第二趟排序后1327［659776493849］第三趟排序后13273

2、8[9776496549]第四趟排序后13273849[76976549]第五趟排序后1327384949[976576]第六趟排序后132738494965[9776]第七趟排序后13273849496576[97]最后排序结果1327384949657697例2.1输入n个数，将n个数按从小到大的顺序输出(n<=10000)。输入样例:84938659776132749输出样例:1327384949657697归纳上述排序过程，具体实现步骤如下：①读入数据存放在a数组中。②在a[1]～a[n]中选择值最小的元素，与第1位置元素交换，则把最

3、小值元素放入a[1]中。③在a[2]～a[n]中选择值最小的元素，与第2位置元素交换，则把最小值元素放入a[2]中，……④直到第n-1个元素与第n个元素比较排序为止。程序实现方法：用两层循环完成算法，外层循环i控制当前序列最小值存放的数组位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。程序如下：#includeusingnamespacestd;constintMAXN=10001;intmain(){intn,k,i,j;floattemp,a[MAXN];cin>>n;for(i=0;i<

4、n;i++)cin>>a[i];//输入n个数for(i=0;i

5、始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。从上述分析中可以看出，每进行一轮的比较之后，n个数的排序规模就转化为n

6、-1个数的排序规模。例如有6个元素需要排序：653412第一趟排序：第二趟排序：第三趟排序：第四趟排序：第五趟排序：五趟结束后，6个整数就已经排序完成。排序过程中，大数慢慢的往后，相当于气泡上升，所以叫冒泡排序。归纳上述排序过程，具体实现步骤如下：①读入数据存放在a数组中。②比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。③对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“冒”到数组第n-1个位置。④n=n-1，如果n不为0就重复前面二步，否则排序完成。程序实现方法：用两层循环完成算法，外层循环i控制每轮

7、要进行多少次的比较，第1轮比较n-1次，第2轮比较n-2次，……，最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否逆序，若逆序就交换这两个元素。【程序实现】#includeusingnamespacestd;constintMAXN=10001;intmain(){intn,i,j;floattemp,a[MAXN];cin>>n;for(i=0;i>a[i];//输入n个数for(i=n-1;i>=1;i--)//进行n-1轮冒泡{for(j=0;j<=i;j++)//

8、每轮进行i次的比较{if(a[j]>a[j+1])//相邻两个元素比较，若逆序就交换swap(a[j],a[j+1]);//交换}}for(i=0;i