要求编写函数select_sort(intarray[],intn)对有n个元素的数组array进行选择排序（由小到大）。在主程序中输入数据元素，并调用此函数数组进行排序...
要求编写函数select_sort(int array[],int n)对有n个元素的数组array进行选择排序（由小到大）。在主程序中输入数据元素，并调用此函数数组进行排序。选择排序的思想是：每一趟从待排序的记录中选出最小的记录，放在已排好序的记录后面。例如：7
2
5
3，第一趟排序后：2
7
5
3第二趟排序后：2
3
5
7第三趟排序后：2
3
5
7
展开选择擅长的领域继续答题？
{@each tagList as item}
${item.tagName}
{@/each}
手机回答更方便，互动更有趣，下载APP

1、正整数n的划分算法int split(int n,int m){
if(n==1
m==1) return 1;
else if(n<m)return split(n,n);
else if(n==m) return split(n,n-1)+1;
else return split(n,m-1)+split(n-m,m)
}
2、对于给定的包含n个元素的数组a[0:n-1]，要求从中找出第k小的元素#define NUM 1001
int a[NUM];
int select(int left,int right,int k){
int (left>=right)return a[left];
int i=left;
int j=right+1;
int pivot=a[left];
while(true){
do{
i=i+1;
}while(a[i]<piovt)
if(i>=j) break;
swap(a[i],a[j])
}
if(j=left+1==k) return piovt;
a[left]=a[j];
a[j]=piovt;
if(j-left+1<k)
return select(j+1,right,k-j+left-1);
else return select(left,j-1,k);
}
3、整数因子分解#include<iostream>
using namespace std;
int total;
void solve(int n){
if(n==1)
total++;
else for(int i=2;i<=n;i++)
if(n%i==0) solve(n/i);
}
int main(){
int n;
while(cin>>n){
total=0;
solve(n);
cout<<total<<endl;
}
}
4、半数集问题半数集递归算法int comp(int n){
int ans=1;
if(n>1) for(int i=1;i<=n/2;i++)
ans+=comp(i);
return ans;
}
记忆式搜索#include<iostream>
#include<memory.h>
using namespace std;
int a[1001];
int comp(int n){
int ans=1;
if(a[n]>0) return a[n];
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans;
return ans;
}
int main(){
int n;
while(cin>>n){
memset(a,0,sizeof(a));
a[1]=1;
cout<<comp(n)<<endl;
}
}
5、输油管道问题采用分治算法计算中位数#include<iostream>
#include<cmath>
#include <sys/time.h>
using namespace std;
int main(){
int n;
int x;
int a[1000];
cin>>n;
for(int i=0;i<n;i++)
cin>>x>>a[i];
int y=select(0,n-1,n/2);
int min=0;
for(int i=0;i<n;i++)
min+=(int)fabs(a[i]-y);
cout<<min<<endl;
}
采用排序算法计算中位数#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
int main(){
int n;
int x;
int a[1000];
cin>>n;
for(int i=0;i<n;i++)
cin>>x>>a[i];
sort(a,a+n);
int min=0;
for(int i=0;i<n;i++)
min+=(int)fabs(a[i]-a[n/2]);
cout<<min<<endl;
}
6、取余运算#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
int mod(int a,int p,int k){
if(p==1) return a%k;
if(p%2) return mod(a%k,p-1,k)*a%k;
else return mod((a*a)%k,p/2,k);
}
int main(){
unsigned a,p,k;
while(cin>>a>>p>>k)
cout<<mod(a,p,k);
}
7、集合全排列#include <iostream>
using namespace std;
void Perm(int list[],int k,int m){
if(k==m){
for(int i=0;i<=m;i++)
cout<<list[i]<<" ";
cout<<endl;
}
else
for(int j=k;j<=m;j++){
swap(list[k],list[j]);
Perm(list,k+1,m);
swap(list[k],list[j]);
}
}
int main()
{
int list[5]={1,2,3,4,5};
Perm(list,0,3);
return 0;
}
8、矩阵连乘问题#define NUM 51
int p[NUM];
int m[NUM][NUM];
int s[NUM][NUM];
void MatrixChain(int n){
for(int i=1;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)
for(int i=1;i<=n;i++){
int j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*[p[i]*p[i];
s[i][j]=i;
for(int k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]p[j];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
}
}
9、最长公共子序列#define NUM 100
int c[NUM][NUM];
int b[NUM][NUM];
void LCSLength(int m,int n,const char x[],char y[]){
int i,j;
for(i=1;i<=m;i++)
c[i][0]=0;
for(i=1;i<=n;i++)
c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][[j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
10、最大子段和#define NUM 101
int a[NUM];
int MaxSum(int n){
int sum=0;
int b=0;
for(int i=1;i<=n;i++){
if(b>0)
b+=a[i];
else b=a[i];
if(b>sum)
sum=b;
}
return sum;
}
11、最大子段和的最优解#define NUM 101
int a[NUM];
int MaxSum(int n,int &besti,int &bestj){
int sum=0;
int b=0;
int begin=0;
for(int i=1;i<=n;i++){
if(b>0)
b+=a[i];
else{
b=a[i];
begin=i;
}
if(b>sum){
sum=b;
besti=begin;
bestj=i;
}
}
return sum;
}
12、0—1背包问题#define NUM 50
#define CAP 1500
int w[NUM];
int v[NUM];
int p[NUM][CAP];
void knapsack(int c,int n){
int jMax=min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
p[n][j]=0;
for(int j=w[n];j<=c;j++)
p[n][j]=v[n];
for(int i=n-1;i>1;i--){
jMax=min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
p[i][j]=p[i+1][j];
for(int j=w[n];j<=c;j++)
p[i][j]=max(p[i+1][j],p[i+1][j-w[n]]+v[i]);
}
p[1][c]=p[2][c];
if(c>=w[1])
p[1][c]=max(p[1][c],p[2][c-w[n]]+v[1]);
}
0—1背包最优解void traceback(int c,int n,int x[]){
for(int i=1;i<n;i++){
if(p[i][c]==p[i+1][c])
x[i]=0;
else {
x[i]=1;
c-=w[i];
}
}
x[n]=(p[n][c])?1:0;
}
13、最长单调递增子序列#define NUM 100
int a[NUM];
int Lls_n2(int n){
int b[NUM]={0};
int i,j;
b[1]=1;
int max=0;
for(i=2;i<=n;i++){
int k=0;
for(j=1;j<i;j++)
if(a[j]<=a[i]&&k<b[j])
k=b[j];
b[i]=k+1;
if(max<b[i])
max=b[i];
}
return max;
}
14、数字三角形问题#define NUM 100
int tri[NUM][NUM];
int triangle(int n){
int i,j;
for(i=n-2;i>=0;i--)
for(j=0;j<=i;j++){
if(tri[i+1][j]>tri[i+1][j+1])
tri[i][j]+=tri[i+1][j];
else tri[i][j]+=tri[i+1][j+1];
}
return tri[0][0];
}
15、Human Gene Functionscin>>first>>secend;
gene[0][0]=0;
for(i=1;i<=secend;i++)
gene[0][i]=gene[0][i-1]+score[4][map[str2[i-1]]];
for(i=1;i<-first;i++)
gene[i][0]=gene[i-1][0]+score[map[str1[i-1]]][4];
int m1,m2,m3;
for(i=1;i<=first;i++)
for(j=1;j<=secend;j++){
m1=gene[i-1][j]+score[map[str1[i-1]]][4];
m2=gene[i][j-1]+score[4][map[str2[i-1]]];
m3=gene[i-1][j-1]+score[map[str1[i-1]][map[str2[i-1]]];
}
FatMouses Speed
struct mouse{
int weight,speed,id;
}mice[1001];
//排序因子int cmp(const void *a,const void *b){
mouse*ta=(mouse*)a;
mouse*tb=(mouse*)b;
if(ta->weight==tb->weight)
return tb->speed-ta->speed;
return ta->weight-tb->weight;
}
//最长单调递增子序列算法int count[1001]={0};
int path[1001]={0};
count[1]=1;
for(int i=2;i<n;i++){
for(int j=1;j<i;j++)
if(mice[i].weight>mice[j].weight&&
mice[i].speed<mice[j].speed)
if(count[i]<count[j]){
count[i]=count[j];
path[i]=j;
}
count[i]++;
}
// 查找最大的序列长度int max=0;
int pos;
for(int i=1;i<n;i++)
if(count[i]>max){
max=count[i];
pos=i;
}
cout<<max;
16、活动安排问题struct action{
int s;
int f;
int index;
}
bool cmp(coust action &a,const action &b){
if(a.f<=b.f)
return true;
return false;
}
void GreedySelector(int n,action a[],bool b[]){
b[1]=true;
int preEnd=1;
for(int i=2;i<=n;i++)
if(a[i].s>=a[preEnd].f){
b[i]=true;
preEnd=i;
}
}
17、背包问题struct bag{
int w;
int v;
double c;
}a[1001];
bool cmp(bag a,bag b){
return a.c>=b.c;
}
double knapsack(int n, bag a[],double c){
double cleft=c;
int i=0;
double b=0;
while(i<n&&a[i].w<cleft){
cleft-=a[i].w;
b+=a[i].v;
i++;
}
if(i<n)
b+=1.0*a[i].v*cleft/a[i].w;
return b;
}
18、Wooden Sticks#define maxN 5001
struct stick{
int l;
int w;
};
stick data[maxN];
int cmp(stick a,stick b){
if(a.l==b.l)
return a.w<b.w;
else if(a.l<b.l)
return true;
return false;
}
int LIS(int n,stick a[]){
int b[maxN];
memset(b,0,sizeof(b));
int i,j,k;
b[0]=1;
for(i=1;i<n;i++){
k=0;
for(j=0;j<i;j++)
if(a[i].w<a[j].w&&k<b[j])
k=b[i];
b[i]=k+1;
}
int max=0;
for(i=0;i<n;i++)
if(b[i]>max)
max=b[i];
return max;
}
19、Gone Fishingvoid greedy(int pos,int time){
if(time<=0)
return;
int i,j;
int fish[MAXN];
int p[MAXN];
int t=0;
for(i=0;i<pos;++i)
fish[i]=f[i];
memset(p,0,sizeof(p));
for(i=0;i<time;i++){
int max=0;
int id=-1;
for(j=0;j<pos;j++)
if(fish[j]>max){
max=fish[j];
id=j;
}
if(id!=-1){
++p[id];
fish[id]-=d[id];
t+=max;
}
else ++p[0];
}
if(t>best){
best=t;
memset(plan,0,sizeof(plan));
for(i=0;i<pos;i++)
plan[i]=p[i];
}
}
for(i=0;i<n-1;++i)
cout<<plan[i]*5;
cout<<plan[n-1]*5;
cout<<best;
20、回溯法-装载问题void Backtrack(int t){
if(t>n){
f(cw>bestw){
for(int i=1;i<=n;i++)
bestx[i]=x[i];
bestw=cw;
}
return;
}
r-=w[t];
if(cw+w[t]<=c){
x[t]=1;
cw+=w[t];
Backtrack(t+1);
cw-=w[t];
}
if(cw+r>bestw){
x[t]=0;
Backtrack(t+1);
}
r+=w[t];
}
21、回溯法-0-1背包问题struct Object{
int w;
int v;
double d;
}Q[NUM];
bool cmp(Object a,Object b){
if(a.d=b.d)
return true;
else return false;
}
void backtrack(int t){
if(i+1>n){
bestv=cv;
return;
}
if(cw+Q[i].w<=c){
cw+=Q[i].w;
cv+=Q[i].v;
backtrack(i+1);
cw-=Q[i].w;
cv-=Q[i].v;
}
if(Bound(i+1)>bestv)
backtrack(i+1);
}
int Bound(int i){
int cleft=c-cw;
int b=cv;
while(i<n&&Q[i].w<=cleft){
cleft-=Q[i].w;
b+=Q[i].v;
i++;
}
if(i<n)
b+=1.0*cleft*Q[i].v/Q[i].w;
return b;
}
22、回溯法-n皇后问题void Backtrack(int t){
int i;
if(t>n){
sum++;
for(i=1;i<=n;i++)
cout<<x[i];
cout<<endl;
}
else
for(i=1;i<=n;i++){
x[t]=i;
if(Place(t))
Backtrack(t+1);
}
}
inline bool Place(int t){
int i;
for(i=1;i<t;i++)
if((abs(t-i)==abx(x[i]-x[t]))
(x[i]==x[t]))
return true;
}
23、回溯法-旅行商问题void Backtrack(int t){
if(t==n){
if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc
bestc==NoEdge)){
for(int 1=1;i<=n;i++)
bestx[i]=x[i];
bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
}
return;
}
else {
for(int i=t;i<=n;i++){
if(a[x[n-1]][x[n]]!=NoEdge&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc
bestc==NoEdge){
swap(x[t],x[i]);
cc+=a[x[t-1]][x[t]];
Backtrack(t+1);
cc-=a[x[t-1]][x[t]];
swap(x[t],x[i]);
}
}
}
}
24、装载问题#define NUM 100
int n;
int c;
int w[NUM];
int MaxLoading(){
queue (int)Q;
Q.push(-1);
int i=0;
int Ew=0;
int bestw=0;
int r=0;
for(int j=1;j<n;j++)
r+=w[j];
while(true){
int wt=Ew+w[i];
if(wt<=c){
if(wt>bestw)
bestw=wt;
if(i<n-1)
Q.push(wt);
}
if(Ew+r>bestw&&i<n-1)
Q.push(Ew);
Ew=Q.front();
Q.pop();
if(Ew==-1){
if(Q.empty())
return bestw;
Q.push(-1);
Ew=Q.front();
Q.pop();
i++;
r-=w[i];
}
}
return bestw;
}
25、Fire Netchar cMap[5][5];
int iBest;
int n;
void solve(int k,int current){
int x,y;
if(k==n*n){
if(current>iBest){
iBest=current;
return ;
}
}
else {
x=k/n;
y=k%n;
if(cMap[x][y]=='.'&&CanPut(x,y)){
cMap[x][y]='0';
solve(k+1,current+1);
cMap[x][y]='.';
}
solve(k+1,current);
}
}
bool CanPut(int row,int col){
int i;
for(i=row-1;i>=0;i--){
if(cMap[i][col]=='0')
return false;
if(cMap[i][col]=='X')
break;
}
for(i=col-1;i>=0;i--){
if(cMap[row][i]=='0')
return false;
if(cMap[row][i]=='X')
break;
}
return true;
}

如题~我知道，第一步要将数组排列，然后呢？...
如题~我知道，第一步要将数组排列，然后呢？
展开选择擅长的领域继续答题？
{@each tagList as item}
${item.tagName}
{@/each}
手机回答更方便，互动更有趣，下载APP
提交成功是否继续回答问题？
手机回答更方便，互动更有趣，下载APP
如果数组元素的范围已知的话,可以参考计数排序的原理.比如数组a是1,3,1,5,2,2,6,2那么可以建一个辅助数组tag[7],其中tag[1]到tag[6]分别表示数组a中是否有相应的元素.那么以下代码即可:for(i=1;i<=6;i++) tag[i]=0;for(i=0;i<8;i++) tag[a[i]]=1;cnt=0;for(i=1;i<=6;i++) a[cnt+]=i;之后a[0]到a[cnt-1]即为所求.