首页 > 代码库 > 归并排序
归并排序
归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。常见的归并排序有两路归并排序（Merge Sort），多相归并排序（Polyphase Merge Sort），Strand排序（Strand Sort）。下面介绍第一种：
（一）两路归并排序
最差时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差空间复杂度：O(n)
稳定性：稳定
两路归并排序（Merge Sort），也就是我们常说的归并排序，也叫合并排序。它是建立在归并操作上的一种有效的排序算法，归并操作即将两个已经排序的序列合并成一个序列的操作。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并操作的基本步骤如下：
1.申请两个与已经排序序列相同大小的空间，并将两个序列拷贝其中；
2.设定最初位置分别为两个已经拷贝排序序列的起始位置，比较两个序列元素的大小，依次选择相对小的元素放到原始序列；
3.重复2直到某一拷贝序列全部放入原始序列，将另一个序列剩下的所有元素直接复制到原始序列尾。
设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
1.分解：将当前区间一分为二，即求分裂点
2.求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
3.组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件：子区间长度为1（一个记录自然有序）。
第一种未优化情况:
template<typename T>void __merge(T arr[], int l, int mid, int r){ // 经测试,传递aux数组的性能效果并不好 T aux[r-l+1]; for( int i = l ; i <= r; i ++ ) aux[i-l] = arr[i]; int i = l, j = mid+1; for( int k = l ; k <= r; k ++ ){ if( i > mid ) { arr[k] = aux[j-l]; j ++;} else if( j > r ){ arr[k] = aux[i-l]; i ++;} else if( aux[i-l] < aux[j-l] ){ arr[k] = aux[i-l]; i ++;} else { arr[k] = aux[j-l]; j ++;} }}// 递归使用归并排序,对arr[l...r]的范围进行排序template<typename T>void __mergeSort(T arr[], int l, int r){ if( l >= r ) return; int mid = (l+r)/2; __mergeSort(arr, l, mid); __mergeSort(arr, mid+1, r); __merge(arr, l, mid, r);}template<typename T>void mergeSort(T arr[], int n){ __mergeSort( arr , 0 , n-1 );}
优化后
template<typename T>void __mergeSort2(T arr[], int l, int r){ // 对于小规模数组,使用插入排序 if( r - l <= 15 ){ insertionSort(arr, l, r); return; } int mid = (l+r)/2; __mergeSort2(arr, l, mid); __mergeSort2(arr, mid+1, r); // 对于arr[mid] <= arr[mid+1]的情况,不进行merge // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失 if( arr[mid] > arr[mid+1] ) __merge(arr, l, mid, r);}
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。