网站怎样做301,网站工程师证书,做网站视频点播难不难,网站建设管理工作情况汇报文章目录解法1#xff1a;直接双重循环求解#xff0c;n*n复杂度解法2#xff1a;采用归并排序求解#xff0c;复杂度nlgn题目链接 http://poj.org/problem?id1804题目大意#xff1a;让一串无序数#xff0c;在只能相邻数字交换的前提下#xff0c;最短的次数变成有序…
文章目录解法1直接双重循环求解n*n复杂度解法2采用归并排序求解复杂度nlgn题目链接 http://poj.org/problem?id1804题目大意让一串无序数在只能相邻数字交换的前提下最短的次数变成有序求该最短次数。该最短次数该序列的逆序数解法1直接双重循环求解n*n复杂度 #includeiostream
#includecstring
using namespace std;
int main()
{const int N 1001;int cyctime,len,len1,sum0;int arr[N];int i0,j0,k0,temp;memset(arr,0,sizeof(int)*N);cin cyctime;for(i 0; i cyctime; i){//cin.clear();cin len;len1len;j0;while(len1--) //先输入数组{cin temp;arr[j] temp;}for(j 0; j len; j) //从前往后依次比较{for(k j1; k len; k){if(arr[j]arr[k]){sum;}}}cout Scenario # i1 : endl;cout sum endl endl;sum 0;}return 0;
}解法2采用归并排序求解复杂度nlgn #includeiostream
#includecstring
using namespace std;
int sum0;
void merge(int *arr,size_t left,size_t mid,size_t right)
{int len right - left 1;int *temp new int [len]; //数组较长时请用new不然栈空间容易溢出size_t index 0;size_t i left, j mid 1;while(i mid j right){if(arr[i]arr[j]){temp[index] arr[i];}else{temp[index] arr[j];sum mid - i 1; //左边数比右边大那么左边剩余的也比其大}//对两边的数组从小到大放入临时空间}while(i mid) //比较完后左半边有没放进去的直接写入{temp[index] arr[i];}while(j right) //比较完后右半边有没有放进去的直接写入{temp[index] arr[j];}for(int k 0;k len;k){arr[left ] temp[k]; //把有序的临时数组写入原来数组的起始位置}delete [] temp; //释放空间temp NULL; //指针置空
}
void divide(int *arr,size_t left,size_t right)
{if(left right){ return;}size_t mid (leftright)/2; //找出区间中部的数将数组分段divide(arr,left,mid); //递归调用对左边继续分段divide(arr,mid1,right); //递归调用对右边继续分段merge(arr,left,mid,right); //对左右两半进行排序合并成一小段有序的数组
}
void mergesort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;divide(arr,left,right);
}int main()
{const int N 1001;int cyctime,len,len1;int arr[N];int i0,j0,temp;memset(arr,0,sizeof(int)*N);cin cyctime;for(i 0; i cyctime; i){//cin.clear();cin len;len1len;j0;while(len1--) //先输入数组{cin temp;arr[j] temp;}mergesort(len,arr);cout Scenario # i1 : endl;cout sum endl endl;sum 0;}return 0;
}由上可看出归并排序求解时间效率更高。
