学步园

这个不知有什么可以优化的。

/*<br /> 归并排序非递归<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> 实质上就是后序遍历二叉树，刚好后序非递归比较生疏，敲一遍无妨。<br /> 话说回来，归并排序用非递归做实在感觉不出有什么优点，栈深一定是O(log(n))，常数也很小。<br /> 就权当作熟悉后序非递归遍历吧。<br /> */</p> <p>#include <stdio.h></p> <p>struct interval {<br /> int l , r;<br /> interval() {}<br /> interval(int _l , int _r):l(_l) , r(_r) {}<br /> };<br /> typedef interval data;<br /> const int MaxN = 1000;<br /> int a[MaxN] , b[MaxN];<br /> class Stack<br /> {<br /> public:<br /> Stack(){top = 0;}<br /> data pop() {<br /> return s[-- top];<br /> }<br /> void push(data now) {<br /> s[top ++] = now;<br /> }<br /> data _top() {<br /> return s[top - 1];<br /> }<br /> bool empty() {<br /> return top == 0;<br /> }<br /> private:<br /> data s[MaxN];<br /> int top;<br /> };<br /> void Merge(int *a , data p)<br /> {<br /> int i , j;<br /> int p1 = p.l , mid = (p.l + p.r) >> 1 , p2 = mid + 1;<br /> for (i = p.l;i <= p.r && p1 <= mid && p2 <= p.r;i ++) {<br /> if (a[p1] > a[p2]) b[i] = a[p2 ++];<br /> else b[i] = a[p1 ++];<br /> }<br /> while (p1 <= mid) b[i ++] = a[p1 ++];<br /> while (p2 <= p.r) b[i ++] = a[p2 ++];<br /> for (i = p.l;i <= p.r;i ++) {<br /> a[i] = b[i];<br /> }<br /> }</p> <p>//非递归归并排序（那应该不叫“归并”了吧。。）<br /> void Sort(int *a , int n)<br /> {<br /> data now(0 , n - 1);<br /> Stack St;<br /> if (now.l >= now.r) return;<br /> St.push(now);<br /> while (now.l != now.r) {<br /> St.push(interval(now.l , now.r = ((now.l + now.r) >> 1)));<br /> }<br /> while (!St.empty()) {<br /> now = St.pop();<br /> while (!St.empty() && now.r == St._top().r) {<br /> now = St.pop();<br /> Merge(a , now);<br /> }<br /> if (!St.empty()) {<br /> now = St._top();<br /> now = interval(1 + ((now.l + now.r) >> 1) , now.r);<br /> St.push(now);<br /> while (now.l != now.r) {<br /> St.push(interval(now.l , now.r = ((now.l + now.r) >> 1)));<br /> }<br /> }<br /> }<br /> }</p> <p>void __test()<br /> {<br /> int n , i;<br /> scanf("%d" , &n);<br /> for (i = 0;i < n;i ++) {<br /> scanf("%d" , &a[i]);<br /> }<br /> Sort(a , n);<br /> puts("归并后的序列：");<br /> for (i = 0;i < n;i ++) {<br /> printf("%d " , a[i]);<br /> }<br /> puts("");<br /> }<br /> int main()<br /> {<br /> __test();<br /> }<br /> /*<br /> 9<br /> 3 2 3 77 8 999 10 4 3<br /> 10<br /> 7 8 77 8 6 4 3 3 2 33<br /> */