Java 合并排序 求程序

Question

越简单越好

Answer 1

百度文库找了一个http://wenku.baidu.com/view/332fd62d453610661ed9f414.html
四、合并排序 1、基本思想
合并排序的基本操作是：首先将待排序序列划分为两个长度相等的子序列；然后分别对两个子序列进行归并排序，得到两个有序的子序列；最后将两个有序的子序列合并成一个有序数列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//划分 MergeSort(A[1,……,n]);//归并排序前半个子序列
MergeSort(A[[n-1,……,2*n]);//归并排序后半个子序列 Merge;//合并 }
2、算法复杂度分析
合并步的时间复杂度为O(n)。合并排序算法的时间复杂度为O(nlog2n)。
3、编程实现
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一个以上的元素，即s<t则进行排序
if(s < t){
int center = (s + t) / 2;
MergeSort(A, tempA, s, center)
;//归并排序前半个子序列
MergeSort(A, tempA, center + 1, t);
//归并排序后半个子序列
Merge(A,tempA, s, center, t);
//合并
}
return tempA;
}

public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;
//n为数据总个数
int i=s;j=m+1;k=s
while(i <= m&& j <= t){
//取A[i]和A[j]中较小者放入tempA[k]
if(A[i]<=A[j]){
tempA[k++] = A[i++]; }
else{
tempA[k++] = A[j++]; } }
if(i<=m) while(i<=m)
tempA[k++]=A[i++];//处理前一个子序列
else while(j<=t)
tempA[k++]=A[j++];//处理后一个子序列
return tempA;
}