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
2021-10-11 10:33:56
3KB
排列
1