Ｃ语言归并排序

0hudu

#include <tchar.h> #include <iostream> #include <algorithm> #include <iterator> //复制函数 //此教程来源于ChinaUnix論壇（http://bbs.chinaunix.net/）查看完整的教程请点：http://bbs.chinaunix.net/thread-1296106-1-1.html template <typename T> void copy(T* begin, T* end, T* out) { while ( begin!=end ) { &nbsp;&nbsp;*out=*begin; &nbsp;&nbsp;++out; &nbsp;&nbsp;++begin; } } //将两个有序数组合并到一个数组中 template <typename T> void merge(T* begin1, T* end1, T* begin2, T* end2, T* out) { for ( ;; ) { &nbsp;&nbsp;if ( begin1!=end1 && begin2!=end2 ) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;if ( *begin1<*begin2 ) &nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;*out=*begin1; &nbsp;&nbsp;&nbsp;&nbsp;++begin1; &nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;*out=*begin2; &nbsp;&nbsp;&nbsp;&nbsp;++begin2; &nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;} &nbsp;&nbsp;else if ( begin1!=end1 ) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;*out=*begin1; &nbsp;&nbsp;&nbsp;++begin1; &nbsp;&nbsp;} &nbsp;&nbsp;else if ( begin2!=end2 ) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;*out=*begin2; &nbsp;&nbsp;&nbsp;++begin2; &nbsp;&nbsp;} &nbsp;&nbsp;else &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;} &nbsp;&nbsp;++out; } } //归并排序 template <typename T> void MergeSort(T data[], int size) { if ( size>1 ) //数组元素要大于两个才有排序的必要 { &nbsp;&nbsp;//将数组二分 &nbsp;&nbsp;int lsize=size/2; &nbsp;&nbsp;int rsize=size-lsize; &nbsp;&nbsp;T* left=new T[lsize]; &nbsp;&nbsp;T* right=new T[rsize]; &nbsp;&nbsp;::copy(data, data+lsize, left); &nbsp;&nbsp;::copy(data+lsize, data+size, right); &nbsp;&nbsp;//递归 &nbsp;&nbsp;MergeSort(left, lsize); &nbsp;&nbsp;MergeSort(right, rsize); &nbsp;&nbsp;//合并 &nbsp;&nbsp;::merge(left, left+lsize, right, right+rsize, data); &nbsp;&nbsp;//删除辅助空间 &nbsp;&nbsp;delete[] left; &nbsp;&nbsp;delete[] right; } } //测试例程 int _tmain(int argc, _TCHAR* argv[]) { int data[10000]; for ( int i=0; i<10000; ++i ) { &nbsp;&nbsp;data[i]=rand()%1000; } MergeSort(data, 10000); std::copy(data, data+10000, std::ostream_iterator<int>(std::cout, " ")); return 0; }

[ 本帖最后由 langue 于 2008-10-25 08:00 编辑 ]