//复杂度：O(nlog2n) //n倍的以2为底n的对数
public static> void msort(T[] arr,T[] tempArr,int start,int end) { 2 3 if(start + 1 < end) { 4 int mid = (start + end) / 2; 5 msort(arr,tempArr,start,mid); 6 msort(arr,tempArr,mid,end); 7 8 if(arr[mid - 1].compareTo(arr[mid]) <= 0) { 9 return;10 }11 12 int A,B,C;13 A = start;14 B = mid;15 C = start;16 while(A < mid && B < end) {17 if(arr[A].compareTo(arr[B]) < 0) {18 tempArr[C] = arr[A];19 A++;20 } else {21 tempArr[C] = arr[B];22 B++;23 }24 C++;25 }26 while(A < mid) {27 tempArr[C] = arr[A];28 A++;29 C++;30 }31 while(B < end) {32 tempArr[C] = arr[B];33 B++;34 C++;35 }36 37 for(int i = start; i != end;++i) {38 arr[i] = tempArr[i];39 }40 }41 }
//测试
1 public static void main(String[] args) {2 3 Integer[] arr = {11,3,5,23,76,435,654,34,543};4 Integer[] tempArr = new Integer[arr.length];5 msort(arr,tempArr,0,arr.length);6 for(int i = 0; i != arr.length;++i) {7 System.out.println(arr[i]);8 }9 }
