归并排序分治法的一个典型且基本的应用. 它的基本思想是: 将对 N 个对象的问题转换成两次对 N/2 个对象的问题. 归并排序减少了数据的比较次数, 转而增加了数据的移动次数, 使得排序速度相对较快. 该算法的递推公式 T(N) = 2T(N/2) + O(N) 表明其算法复杂度上限为 O(NlogN). 下面是其 C++ 代码:
- #include<cstring>
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- int innersort(int* A,int left,int right,int* CPY)
- {//[left,mid]and[mid+1,right];
- if(right==left)return 0;
- int mid=(left+right)/2;
- int i=left,k=mid+1;
- int cur=left;
- while(i!=mid+1&&k!=right+1)
- {
- if(A[i]>A[k])CPY[cur++]=A[k++];
- else CPY[cur++]=A[i++];
- }// 一定有一侧的数据会最先完成排序
- while(i!=mid+1)CPY[cur++]=A[i++];
- while(k!=right+1)CPY[cur++]=A[k++];// 对剩余的一侧数据一次添加进入 CPY 数组即可
- memcpy(A+left,CPY+left,sizeof(int)*(right-left+1));// 复制回到原数组
- return 0;
- }
- int merger(int* A,int left,int right,int* CPY)
- {//[left,mid]and[mid+1,right];
- if(left<right)
- {
- int center=(left+right)/2;
- // 中点的归属需要特别考虑
- merger(A,left,center,CPY);
- merger(A,center+1,right,CPY);
- innersort(A,left,right,CPY);
- }
- return 0;
- }
- int mergesort(int* A,int* Aend)
- {//[left,right);
- int right=Aend-A;
- int* temp=new int[right+1];// 临时数组开得大了一点
- merger(A,0,right-1,temp);
- // 数组的边界问题与分割方案问题一直是关注点
- delete[] temp;
- return 0;
- }
- int main()
- {
- int aim[]={3,5,2,6,7,3,2,6,2,6,3,7,3,2};
- mergesort(aim,aim+14);
- for(int i=0;i<14;i++)
- {
- printf("%d",aim[i]);
- }
- printf("\n");
- return 0;
- }
归并排序中的比较次数是所有排序中最少的. 原因是, 它一开始是不断地划分, 比较只发生在合并各个有序的子数组时.
因此, JAVA 的泛型排序类库中实现的就是归并排序. 因为: 对于 JAVA 而言, 比较两个对象的操作代价是很大的 (根据 Comparable 接口的 compareTo 方法进行比较), 而移动两个对象, 其实质移动的是引用, 代价比较小.(排序本质上是两种操作: 比较操作和移动操作)
来源: http://www.bubuko.com/infodetail-3421485.html