问题:将n个键排列为非递减顺序。
输入:正整数n;键的数组S,其索引范围为1-n,
输出,数组S,其中键按照非递减排序。
//C/C++
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//归并排序
void Merge(int h,int m,const int U[],const int V[],int S[])
{
int i=0,j=0,k=0;
while(i<h&&j<m)
{
if(U[i]<V[j])
S[k++]=U[i++];
else
{
S[k++]=V[j++];
}
}
if(i>=h)//将V[j]至V[m]复制到S[K]至S[h+m]中
while(j<m)
S[k++]=V[j++];
else
while(i<h)
S[k++]=U[i++];
}
void mergesort(int n,int S[])
{
if(n>1)
{
const int h=n/2,m=n-h;
int U[h],V[m];
for(int i=0;i<h;i++)
U[i]=S[i];//将S[]数组的前h项移动到数组U;
int temp=h;
for(int i=0;i<m;i++)
V[i]=S[temp++];//将S[]数组的后m项移动到数组V;
mergesort(h,U);
mergesort(m,V);
Merge(h,m,U,V,S);//可以合并两个有序数组的算法
}
}
int main()
{
int S[100]={0};
for(int i=0;i<8;i++)
cin>>S[i];
mergesort(8,S);
for(int i=0;i<8;i++)
{
cout<<S[i]<<endl;
}
return 0;
}