归并排序

 1 package com.java;
 2 import java.util.Arrays;
 3 
 4 /**
 5  * 分治算法
 6  * 基本思路：
 7  * 对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，
 8  * 这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
 9  * 具体步骤如下：
10  * 1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
11  * 2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
12  * 3、合并：将各个子问题的解合并为原问题的解。
13  */
14 
15 /**
16  * 归并排序算法完全遵循分治模式，归并排序的基本操作如下：
17  * 1、分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
18  * 2、解决：使用归并排序递归地对两个子序列进行排序。
19  * 3、合并：合并两个已排序的子序列以产生已排序的答案。
20  */
21 
22 public class MergeSort {
23     public static void main(String[] args) {
24         int[] A = {15, 5, 3, 9, 4, 82, 35, 45, 7, 11};
25         System.out.println("原始数据： " + Arrays.toString(A));
26 
27         Merge_sort(A, 0, A.length - 1);
28         System.out.println("输出结果： " + Arrays.toString(A));
29     }
30 
31     public static void Merge_sort(int[] A, int p, int r) {
32         int q = (p + r) / 2;
33         if (p  r) {
34             //递归调用左分区
35             Merge_sort(A, p, q);
36             //递归调用右分区
37             Merge_sort(A, q + 1, r);
38             //归并排序数据元素
39             Merge(A, p, q, r);
40         }
41     }
42 
43     public static void Merge(int[] A, int p, int q, int r) {
44         int[] tmp = new int[r - p + 1];//声明一个临时数组，长度为要归并数组的长度
45         int i = p;   //记住左边数组第一个元素的下标
46         int j = q + 1; //记住右边数组第一个元素的下标
47         int k = 0;
48         while (i  r) {
49             //左边数组元素和右边数组元素比较，把小的元素赋给临时数组
50             if (A[i]  A[j]) {
51                 tmp[k++] = A[i++];
52             } else {
53                 tmp[k++] = A[j++];
54             }
55         }
56         //把左边剩余的数组元素赋给临时数组
57         while (i  q) {
58             tmp[k++] = A[i++];
59         }
60         //把右边剩余的数组元素赋给临时数组
61         while (j  r) {
62             tmp[k++] = A[j++];
63         }
64         //用临时数组元素覆盖原数组元素
65         for (int k2 = 0; k2 ) {
66             A[k2 + p] = tmp[k2];
67         }
68     }
69 }