|
- UID
- 1029342
- 性别
- 男
|
之前看了选择和插入排序，这两个算法是的时间复杂度均为O(n^2),而随着问题规模n的增大，插入和选择排序都比较慢。
归并排序时的时间复杂度为O（nlgn) 其主要思想是分治法(divide and conquer)，分就是要将n个元素的序列划分为两个序列，再将两个序列划分为4个序列，
直到每个序列只有一个元素，最后，再将两个有序序列归并成一个有序的序列。
例如两个序列：
要归并成一个有序的序列，按照我们常规的方法，我们每次从两个列表开头元素选取较小的一个，直到某一个列表到达底部，再将另一个剩下部分顺序取出。其实如果将每个元素最后添加一个最大值，则无需判断是否达到列表尽头。
代码如下：merge函数的功能为将A中[low,mid],[mid+1,high]归并成一个有序的片段。
[url=] [/url]
template<class T> void merge(T A[],int low,int mid,int high){ //low to mid as the left array mid+1 to high as the right array int llen = mid-low+2; int rlen = high-mid+1; T *left = (T*)new T[llen]; T *right = (T*)new T[rlen]; //copy the low to mid to the temp array left for (int i=0;i<llen-1;i++) { left = A[low+i]; } for (i=0;i<rlen-1;i++) { right = A[mid+1+i]; } //set the sentinel left[llen-1] = numeric_limits<T>::max(); right[rlen-1]= numeric_limits<T>::max(); //merge the two array and copy to A[low,high]; int j = 0; int k = 0; for (i = low; i < high+1 ;i++) { if (left[j] < right[k]) { A = left[j]; j++; } else { A = right[k]; k++; } }
delete [] left;
delete [] right;}[url=][/url]
归并排序就是多次调用merge
[url=][/url]
template<class T> merge_sort(T A[],int low,int high){ int mid = (low+high)/2; if (low < high) { merge_sort(A,low,mid); merge_sort(A,mid+1,high); merge(A,low,mid,high); }}[url=][/url]
这是一个递归算法，这个算法的理解其实可以借助下面这个图：
对于原始的数组2,1,3,8,5,7,6,4,10，在整个过程执行的是顺序是途中红色编号1-20。虽然我们描述中说的是程序先分解，再归并，但实际过程是一边分解一边归并，前半部分分先排好序，后半部分再拍好，最后整个归并为一个完整的序列，途中的merge过程它所在层的两个序列的merge过程：下图展示了每个merge过程对作用于数组的哪部分（红色）。
整个过程就像一个动态的树，执行顺序就是对树的先序遍历顺序。
最后实验验证，对10000个倒序的数组进行排序，直接插入排序需1024ms，二归并排序只需20ms。 |
|
