归并排序-Java实现

 1 /**
 2  * Created by hardaway on 2018/7/23.
 3  * 归并排序
 4  * 分治思想，分：划分为规模更小的相似问题；治：将两个有序子序列整合为一个。
 5  * 时间复杂度O(NlgN)， 最好，最坏，平均复杂度是O(NlgN)
 6  * 稳定排序
 7  */
 8 public class mergeSorting {
 9     public void sort(int[] arr){
10         sort(arr,0,arr.length-1);
11     }
12     public void sort(int[] arr, int head, int tail){
13         if(head>=tail)
14             return;
15         int mid = head+(tail-head)/2;
16         sort(arr, head, mid);
17         sort(arr, mid+1, tail);
18         format(arr,head,mid,tail);
19     }
20     public void format(int[] arr, int head, int mid, int tail){
21         int[] small = Arrays.copyOfRange(arr,head,tail+1);
22         int tp1 = 0;
23         int tp2 = mid-head+1;
24         int i = head;
25         int end1 = mid-head;
26         int end2 = tail-head;
27         while(tp1<=end1&&tp2<=end2){
28             if(small[tp1]<=small[tp2])
29                 arr[i++] = small[tp1++];
30             else
31                 arr[i++] = small[tp2++];
32         }
33         while(tp1<=end1){
34             arr[i++] = small[tp1++];
35         }
36         while (tp2<=end2){
37             arr[i++] = small[tp2++];
38         }
39     }
40 
41     public static void main(String[] args) {
42         int[] arr = {9,3,1,4,2,7,8,6,5};
43         System.out.println(Arrays.toString(arr));
44         mergeSorting m = new mergeSorting();
45         m.sort(arr);
46         System.out.println(Arrays.toString(arr));
47     }
48 }