首页 > 代码库 > hdu--3743--归并排序<自顶向下&&自底向上>2种写法
hdu--3743--归并排序<自顶向下&&自底向上>2种写法
有些人说 归并排序的递归版本实用性差 可读性强
非递归版本恰好相反
我觉得 也没那么明显差距吧....
其实非递归版本也不难理解的
假如 我们需要进行排序的数组的长度为 len 每次的子排序数组区间为size
那么我们首先将它拆成 len个size为1的小区间 然后2个相邻的进行合并merge排序 这时候 你需要判断一下 能否恰好一一合并 因为是奇数就不行了
这样 我们进行了第一趟归并 然后size*2 然后将size为2的2个相邻区间进行合并 继续判断..
一直到size>len 结束循环
...
传送----这篇写的不错
然后这题 我分别拿 递归的归并 非递归的归并进行了测试 没什么区别
其中 对于归并中的辅助数组我们可以选择直接开好足够大的静态数组 或者选择 new[right-left+1]来开 当然 我们也知道new的话会比较耗时 但同时也节省了内存
************************
差点忘记说这题了 毫无特色=-= 或许是因为我做了上一题的原因 只要你能读懂英文...#24 就是完全一样的啊...
1 #include <iostream> 2 using namespace std; 3 4 typedef long long LL; 5 LL sum; 6 const int size = 1000010; 7 int arr[size]; 8 int temp[size]; 9 10 void merge_sort( int l , int r )11 {12 int p , q , mid , i;13 if( r-l > 1 )14 {15 p = l;16 mid = l + (r-l)/2;17 q = mid;18 i = l;19 merge_sort( l , mid );20 merge_sort( mid , r );21 while( p<mid || q<r )22 {23 if( q>=r || ( p<mid && arr[p]<=arr[q]) )24 {25 temp[i++] = arr[p++];26 }27 else28 {29 temp[i++] = arr[q++];30 sum += mid-p;31 }32 }33 for( i = l ; i < r ; i++ )34 arr[i] = temp[i];35 }36 }37 38 int main()39 {40 cin.sync_with_stdio(false);41 int n;42 while( cin >> n )43 {44 sum = 0;45 for( int i = 0 ; i<n ; i++ )46 cin >> arr[i];47 merge_sort( 0 , n );48 cout << sum << endl;49 }50 return 0;51 }
1 #include <iostream> 2 using namespace std; 3 4 typedef long long LL; 5 LL sum; 6 const int size = 1000010; 7 int arr[size]; 8 int temp[size]; 9 10 void merge( int left , int mid , int right )11 {12 int p , q , i;13 p = i = left , q = mid+1;14 while( p<=mid || q<=right )15 {16 if( q>right || ( p<=mid && arr[p]<=arr[q] ) )17 {18 temp[i++] = arr[p++];19 }20 else21 {22 temp[i++] = arr[q++];23 sum += mid-p+1;24 }25 }26 for( i = left ; i<=right ; i++ )27 {28 arr[i] = temp[i];29 }30 }31 32 void merge_sort( int n )33 {34 int left , mid , right , len;35 len = 1;36 while( len <= n-1 )37 {38 left = 0;39 while( left+len <= n-1 )40 {41 mid = left + len - 1;42 right = mid + len;43 if( right>n-1 )44 right = n-1;45 merge( left , mid , right );46 left = right + 1;47 }48 len *= 2;49 }50 }51 52 int main()53 {54 cin.sync_with_stdio(false);55 int n;56 while( cin >> n )57 {58 sum = 0;59 for( int i = 0 ; i<n ; i++ )60 {61 cin >> arr[i];62 }63 merge_sort( n );64 cout << sum << endl;65 }66 return 0;67 }
1 #include <iostream> 2 using namespace std; 3 4 typedef long long LL; 5 LL sum; 6 const int size = 1000010; 7 int arr[size]; 8 9 void merge( int left , int mid , int right )10 {11 int p , q , i;12 p = left , q = mid+1;13 int* temp = new int[right-left+1];14 i = 0;15 while( p<=mid || q<=right )16 {17 if( q>right || ( p<=mid && arr[p]<=arr[q] ) )18 {19 temp[i++] = arr[p++];20 }21 else22 {23 temp[i++] = arr[q++];24 sum += mid-p+1;25 }26 }27 for( int k = 0 , i = left ; i<=right ; i++ , k++ )28 {29 arr[i] = temp[k];30 }31 delete []temp;32 }33 34 void merge_sort( int n )35 {36 int left , mid , right , len;37 len = 1;38 while( len <= n-1 )39 {40 left = 0;41 while( left+len <= n-1 )42 {43 mid = left + len - 1;44 right = mid + len;45 if( right>n-1 )46 right = n-1;47 merge( left , mid , right );48 left = right + 1;49 }50 len *= 2;51 }52 }53 54 int main()55 {56 cin.sync_with_stdio(false);57 int n;58 while( cin >> n )59 {60 sum = 0;61 for( int i = 0 ; i<n ; i++ )62 {63 cin >> arr[i];64 }65 merge_sort( n );66 cout << sum << endl;67 }68 return 0;69 }
today:
寒门出贵子，
白屋出公卿。
将相本无种，
男儿当自强。
hdu--3743--归并排序<自顶向下&&自底向上>2种写法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。