排列问题再讨论

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