java 算法之归并排序详解及实现代码

时间:2022-09-22 14:37:16

java 算法归并排序详解

一、思想

归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来;  

二、概念

归并:将两个有序的数组归并成一个更大的有序数组;  

三、特点

优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比;

缺点:需要额外的空间和N成正比; 

 四、实现方法

将两个不同的有序数组归并到第三个数组中;

先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间; 

五、代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
 * 归并排序
 
 * @author pengcx
 
 */
public class Merge extends Sort { 
  /** 归并所需的辅助数组 */
  private static Comparable[] aux; 
  
  public static void main(String[] args) { 
    String[] a = { "d", "a", "w", "b", "q" }; 
    Merge.sort(a); 
    show(a); 
  
  
  public static void sort(Comparable[] a) { 
    aux = new Comparable[a.length]; 
    sort(a, 0, a.length - 1); 
  
  
  /**
  * 排序数组的a[lo]至a[hi]元素
  
  * @param a
  *      数组a
  * @param lo
  *      最小元素位置lo
  * @param hi
  *      最大元素位置hi
  */
  private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) { 
      return
    
  
    // 计算数组中间位置 
    int mid = lo + (hi - lo) / 2
    // 排序数组a左边的元素 
    sort(a, lo, mid); 
    // 排序数组a右边的元素 
    sort(a, mid + 1, hi); 
    // 合并数组a左边和右边的元素 
    merge(a, lo, mid, hi); 
  
  
  /**
  * 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并
  
  * @param a
  *      合并的数组a
  * @param lo
  *      最小数组元素lo
  * @param mid
  *      中间元素位置mid
  * @param hi
  *      最大元素位置hi
  */
  public static void merge(Comparable[] a, int lo, int mid, int hi) { 
    int i = lo, j = mid + 1
  
    for (int k = lo; k <= hi; k++) { 
      aux[k] = a[k]; 
    
  
    for (int k = lo; k <= hi; k++) { 
      // 如果左边的元素用尽,取右边的元素 
      if (i > mid) { 
        a[k] = aux[j++]; 
      
      // 如果右边的元素用尽,取左边的元素 
      else if (j > hi) { 
        a[k] = aux[i++]; 
      
      // 如果右半边的当前元素小于左半边的当前元素,取右半边元素 
      else if (less(aux[j], aux[i])) { 
        a[k] = aux[j++]; 
      
      // 如果右半边的当前元素大于等于左半边的当前元素,取左半边元素 
      else
        a[k] = aux[i++]; 
      
    
  

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/p106786860/article/details/17750515