内容分析排序.pptx

排 序II东北师大附中谷方明简单排序——冒泡排序void bubblesort(int a[],int n){ int i,j; for(i=n;i=1;i--) for(j=1;ji;j++) if(a[j]a[j+1]) swap(p[j],p[j+1]);}1~i交换逆序对T(n)=n(n-1)/2O(n2)简单排序——选择排序void selectsort(int a[],int n){ int i,j,k; for(i=1;in;i++){ k=i; for(j=i+1;j=n;j++) if(a[j]a[k]) k=j; swap(a[i],a[k]); } }i~n，选择最小放到 i 处 T(n)=n(n-1)/2 O(n2)简单排序——插入排序void insertsort(int a[],int n){ int i,j,k; for(i=2;i=n;i++) { k=a[i]; for(j=i-1;j=1;j--) if(a[j]k) a[j+1]=a[j];else break; a[j+1]=k; }}把第i个数插到1~ i-1 中，保持有序。T(n)=n(n-1)/2 O(n2)例1. pj2009_2 分数线划定score【题目描述】 世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。【输入】 第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。【输出】 第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。 从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。【输入样例】6 31000 903239 882390 957231 841005 951001 88【输出样例】88 51005 952390 951000 901001 883239 88【提示】【样例说明】因为88有重分，所以所有成绩大于等于88 的选手都可以进入面试，故最终有5 个人进入面试。 算法思想：按题目要求模拟由于N=5000，使用最简单的冒泡排序即可S1:输入N、M；N个人的考号和成绩S2：按笔试分数和考号排序S3:根据m定分数线和实际人数S4： 输出分数线、实际人数；按序输出每人的考号和信息快排void quicksort(int a[],int l,int r){ if(l=r) return; int i=l,j=r; while(i!=j) { while(a[j]a[i]) j--; swap(a[i],a[j]); while(a[i]a[j]) i++; swap(a[i],a[j]); } quicksort(a,l,i-1); quicksort(a,i+1,r); }用a[l]快速分划 平均O(nlogn)，最坏O(n2)例2 tg2007_1 统计数字 count 【问题描述】?某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。。【输入】输入文件count.in包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1每行一个自然数。【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。【输入输出样例】【限制】40%的数据满足：1=n=100080%的数据满足：1=n的数据满足：1=n=200000，每个数均不超过1500 000 000（1.5*109）count.incount.out82424510021002 34 25 110