首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1579字,纯文字阅读大概需要3分钟。
内容图文
实践题目名称:找第k小的数
问题描述:
设计一个平均时间为O(n)的算法,在n(1<=n<=1000)个无序的整数中找出第k小的数。
提示:函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x(如a[left])对a[left]~a[right]进行划分,划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数,通过调用partition函数获得划分点,判断划分点是否第k小,若不是,递归调用find函数继续在左段或右段查找。
输入格式:
输入有两行:
第一行是n和k,0<k<=n<=10000
第二行是n个整数
输出格式:
输出第k小的数
输入样例:
在这里给出一组输入。例如:
10 4
2 8 9 0 1 3 6 7 8 2
输出样例:
在这里给出相应的输出。例如:
2
算法描述:
题设提示使用快速排序,在总共有x个数的时候,每层递归时所选取的参照数在该层递归排序完后,其必定位于次数列第y个空间,前面y-1个数都比它小,后面x-y个数都大于它,即为它即是该数列中第y小的数。因此只需在快速排序的过程中找到在排序后位于第k个空间的参照数,这个数即为我们所要求的第k小的数。
1 #include<bits/stdc++.h> 2usingnamespace std; 3 4int partition(int a[],int left,int right){ 5int l=left,r=right+1; 6int x=a[left],s; 7while(l<r){ 8while(a[++l]<x&&l<r); 9while(a[--r]>x); 10if(l>=r)break; 11 swap(a[l],a[r]); 12 } 13 a[left]=a[r]; 14 a[r]=x; 15return r; 16} 1718int find(int a[],int left,int right,int k){ 19if(left<=right){ 20int m=partition(a,left,right); 21if(m==k)return a[m]; 22if(m>k){ 23 find(a,left,m-1,k); 24 } 25else find(a,m+1,right,k); 26 } 27} 2829int main(){ 30int n,k,a[10002]; 31 cin >> n >> k; 32for(int i=1;i<=n;i++){ 33 cin >> a[i]; 34 } 35int result = find(a,1,n,k); 36 cout << result; 37return0; 38 }
算法时间及空间复杂度分析(要有分析过程):
最优时间复杂度为T(1),即为当k=(int)n/2的情况,最差时间复杂度为T(nlogn),即为在快速排序完全完成时才找到的情况。
心得体会(对本次实践收获及疑惑进行总结)
这道题主要看对快速排序算法的熟悉程度,思考的重点是区分递归中的层次和找到判定第k小的数的插入位置,对理解递归和快速排序比较有帮助。
原文:https://www.cnblogs.com/lostforlo/p/13765631.html
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。