【文件属性】：
文件名称：排列问题再讨论
文件大小：3KB
文件格式：TXT
更新时间：2016-11-13 14:37:55
排列
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
--------------------------------------------------------------------------------
