java算法----排序----（5）归并排序

 1 package log;
 2 
 3 import java.util.Arrays;
 4 
 5 public class Test4 {
 6 
 7     /**
 8      * java算法---归并排序
 9      * 
10      * @param args
11      */
12     public static void main(String[] args) {
13         // 需要排序的数组
14         int arr[] = { 49, 20, 36, 51, 18, 94, 61, 31, 50 };
15         // 循环输出该数组内容
16         System.out.println("排序之前：");
17         for (int a : arr) {
18             System.out.print(a + "	");
19         }
20         System.out.println();
21 
22         sort(arr, 0, arr.length - 1);
23         // 循环输出该数组内容
24         System.out.println("排序之后：");
25         for (int a : arr) {
26             System.out.print(a + "	");
27         }
28         System.out.println();
29 
30     }
31 
32     public static void merge(int[] list, int left, int center, int right) {
33         int[] tempArr = new int[list.length];
34         int mid = center + 1;
35         int third = left;
36         int temp = left;
37         while (left <= center && mid <= right) {
38             if (list[left] <= list[mid]) {
39                 tempArr[third++] = list[left++];
40             } else {
41                 tempArr[third++] = list[mid++];
42             }
43         }
44         while (mid <= right) {
45             tempArr[third++] = list[mid++];
46         }
47         while (left <= center) {
48             tempArr[third++] = list[left++];
49         }
50         while (temp <= right) {
51             list[temp] = tempArr[temp++];
52         }
53         System.out.println(Arrays.toString(list));
54     }
55 
56     public static void sort(int[] list, int left, int right) {
57         if (left < right) {
58             int center = (left + right) / 2;
59             sort(list, left, center);
60             sort(list, center + 1, right);
61             merge(list, left, center, right);
62         }
63     }
64 
65 }

下面是控制台的输出结果

归并排序是将两个或者两个以上有序表合并成一个新的有序表，即把带排序序列分为若干个子序列，每个子序列都是有序的。然后再把有序子序列合并为整体有序序列。