选择排序：稳定
适用于：数据量大，并且对稳定性有要求的情况。
public class MergeSort { public static void main(String[] args) { int[] a= {3,4,2,5,1}; mergeSort(a,0,a.length-1); System.out.print(Arrays.toString(a)); } //合并有序子序列 public static void merge(int[] array,int p,int q,int r) { int n1=q-p+1; int n2=r-q; int i=0; int j=0; int k=0; int[] L=new int[n1]; int[] R=new int[n2]; for( i=0,k=p;i<n1;i++,k++) { L[i]=array[k]; } for( i=0,k=q+1;i<n2;i++,k++) { R[i]=array[k]; } for( i=0,j=0,k=p;i<n1&&j<n2;k++) { if(L[i]<R[j]) { array[k]=L[i++]; }else { array[k]=R[j++]; } } if(i<n1) { for(j=i;j<n1;j++,k++) { array[k]=L[j]; } } if(j<n2) { for(i=j;i<n2;i++,k++) { array[k]=R[i]; } } } public static void mergeSort(int[] array,int p,int r) { if(p<r) { int q=(p+r)/2; mergeSort(array,p,q); mergeSort(array,q+1,r); merge(array,p,q,r); } }}
转载于:https://www.cnblogs.com/sgbe/p/10768076.html
