《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告1

?

實(shí)驗(yàn)名稱: 統(tǒng)計(jì)一個(gè)排列中逆序?qū)Φ膫€(gè)數(shù)

系 ???別:xxx???????????

專????業(yè):xxx? ? ? ? ? ?

班????級:xxx

姓 ???名:xxx? ? ? ? ??

學(xué)????號:xxx

實(shí)驗(yàn)日期:xx年xx月xx日

1.??算法題目

統(tǒng)計(jì)一個(gè)排列中逆序?qū)Φ膫€(gè)數(shù)

?

2. ?設(shè)計(jì)思路與步驟

通過歸并排序，在排序的過程中統(tǒng)計(jì)逆序的的個(gè)數(shù)。

3. ?算法實(shí)現(xiàn)與代碼

#include<stdio.h>

int num=0;

void Merge(int *A,int *B,int first,int m,int end);

void Inversion(int *A,int *B,int first,int end);

int main(){

int i,n;

int A[100];

int B[100];

printf("請輸入要排序的個(gè)數(shù)；");

scanf("%d",&n);

for(i=1;i<=n;i++){

printf("請輸入要排序的元素:\n");

scanf("%d",&A[i]);

}

Inversion(A,B,1,n);

for(i=1;i<=n;i++){

}

printf("逆序?qū)€(gè)數(shù)為：%d",num);

}

void Inversion(int *A,int *B,int first,int end){

if(first<end){

int m, i;

m=(first+end)/2;

Inversion(A,B,first,m);

Inversion(A,B,m+1,end);

Merge(A,B,first,m,end);

for(i=first;i<=end;i++){

A[i]=B[i];

}

}

}

void Merge(int *A,int *B,int first,int m,int end){

int i=first;

int j=m+1;

int k=first;

while(i<=m&&j<=end){

if(A[i]<=A[j]){

B[k++]=A[i++];

}

else{

B[k++]=A[j++];

num+=m-i+1;

}

}

while(i<=m){

B[k++]=A[i++];

}

while(j<=end){

B[k++]=A[j++];

}

}

?

4. ?測試用例與結(jié)果

?

5. ?問題與總結(jié):

答：xxx。