开发工具:
文件大小: 3kb
下载次数: 0
上传时间: 2013-10-24
详细说明： 11086 排序问题再探讨 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 Description 此题以程序填空的形式进行，请将下列程序框架复制到本机，并按下面要求填充完整后再用g++编译器提交， 在不改变程序框架情况下，可以自由添加所需的函数和变量，或修改合适的函数参数。 1，请改写一个"递归"的插入排序，排序a[0…n-1]，先递归的排序a[0…n-2]，然后再将a[n-1]插入到已排序的a[0…n-2]中去。 2，自然合并排序，书上2.7节最后介绍的算法，请实现它。 3，快速排序，选择"中位数"作为轴值然后进行左右段分区，请实现它。 #include #include "stdlib.h" using namespace std; const int SIZE = 10001; int a[SIZE]; void RecurInsertionSort(int p, int q) //对a[p…q]的递归插入排序，参数可根据自己需要修改。 { …… } void NaturalMergeSort(int n) //对n个元素的自然合并排序，参数可根据自己需要修改。 { …… } int Partition(int x, int p, int q) //以x为基准元素划分a[p…q],返回基准下标. 书上2.8节有。参数可根据自己需要修改。 { …… } int median(int p, int q) //挑出a[p…q]的中位数,并返回中位数，参数可根据自己需要修改。 { …… } void QuickSort(int p,int q) //参数可根据自己需要修改。 { if(p>=q)return; int x = median(p, q); int i=Partition(x,p,q); QuickSort(p,i-1); QuickSort(i+1,q);//递归 } int main() { int i,n; cin >> n; //递归插入排序 for(i=0;i> a[i]; } RecurInsertionSort(0,n-1); cout << "Insert sort: "; for(i=0;i> a[i]; } NaturalMergeSort(n); cout << "\nNatural merge sort: "; for(i=0;i> a[i]; } QuickSort(0, n-1); cout << "\nQuick sort: "; for(i=0;i 1) { RecurInsertionSort(p, q-1); Insert(p,q); } else return; } 2，自然合并排序 参照书上的思想. 3.选择问题：选中位数。用随机选轴值的“快速选择算法”获得，随机选轴值可以获得比较好的性能，倒是无须用“中间的中间”选轴值那么麻烦。 作者 zhengchan -------------------------------------------------------------------------------- ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
