本文共 1725 字，大约阅读时间需要 5 分钟。

非递归版的归并排序，省略了中间的栈空间，直接申请一段O(n)的地址空间即可，因此空间复杂度为O(n),时间复杂度为O(nlogn);

实现：

#include
   
    #include
    
     void merge1(int a[], int tmp[], int left, int right, int r_end)//实际例程 	{		int tmp_pos, l_end;		int element_num;		tmp_pos = left;		l_end = right-1;		element_num = r_end-left+1;				while(left <= l_end && right <= r_end){			if(a[left] <= a[right]){				tmp[tmp_pos++] = a[left++];			}			else				tmp[tmp_pos++] = a[right++];		}		while(left <= l_end){			tmp[tmp_pos++] = a[left++];		}		while(right <= r_end){			tmp[tmp_pos++] = a[right++];		}		} void merge_once(int a[], int tmp[], int n, int step)//当前step下的一趟 	{		int i;		int j; 		for(i = 0; i <= n-2*step; i += 2*step ){//保证只合并完整的两个子序列 			merge1(a, tmp, i, i + step, i + 2*step - 1);		}		//结束时 i 跳到下一次归并子序列起点（如果还有子序列的话） 		if(i + step < n+1)// 判断是否超过一个子序列（不会是2个子序列） 			merge1(a, tmp, i, i+step, n-1);		else{			for(j = i; j < n; j++ )				tmp[j] = a[j]; 		}	//*************************************////下面这个 保证每次 归并完 都把结果 重新保存到数组 a中	////*************************************//			for(i = 0; i < n; i++ ){			a[i] = tmp[i];		}		}void merge_sort(int a[], int n) //驱动程序 	{		int *tmp;		int step = 1;		tmp = (int *)malloc(sizeof(int)*n);// 不要忘记 乘 n 		if(tmp != NULL){			while(step < n){				merge_once(a, tmp, n, step);				step *= 2;	//下面这个 同样是保证最后的结果都保存在 a 数组中 并且比上面的方法更高效////************************************************************//								 	//				merge_once(tmp, a, n, step);              ////				step *= 2; 								 ////******************************************************//			}		}	}	int main()	{		int a[] = {5, 6, 8, 1, 10, 23, 12, 2, 9, 11};		int n;		n = sizeof(a)/sizeof(a[0]);		merge_sort(a, n);				int i;		for(i = 0; i < n; i++ ){			printf("%d ",a[i]);		}				return 0;		}
    
   

转载地址：http://lximi.baihongyu.com/