归并排序

2020-02-01/2020-02-01
0 评论 116 浏览

参考链接:
图解排序算法(四)之归并排序


  归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略【分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"整合"在一起,即分而治之】。

  根据图所示,首先将序列递归分解,直到分成的都是一个数,然后递归返回,数组中的小单元开始进行合并,在合并的时候进行排序,每个合成的序列都为有序序列。接下来,我们来看最后一次合并。


代码实现中,先将原数组数据复制进了temp数组,然后将合并形成的序列填进了原数组,Java实现:

 1import java.util.ArrayList;
 2import java.util.Arrays;
 3import java.util.Collections;
 4import java.util.List;
 5
 6public class MergeSort {
 7    //算法类不允许产生任何实例
 8    private MergeSort() {
 9    }
10
11    //将arr[l...mid] 和arr[mid+1....r] 两部分进行归并
12    private static <T extends Comparable<T>> void merge(T[] arr, int l, int mid, int r) {
13        T[] temp = Arrays.copyOfRange(arr, l, r + 1);
14        //初始化,i指向左半部分的起始;j指向右半部分,索引位置为mid+1
15        int i = l, j = mid + 1;
16        for (int k = l; k <= r; k++) {
17            if (i > mid) {
18                //左半部分元素已经全部处理完毕
19                arr[k] = temp[j - l];
20                j++;
21            } else if (j > r) {
22                //右半部分元素已经全部处理完毕
23                arr[k] = temp[i - l];
24                i++;
25            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
26                //左半部分所指元素<右半部分所指元素
27                arr[k] = temp[i - l];
28                i++;
29            } else {
30                arr[k] = temp[j - l];
31                j++;
32            }
33        }
34    }
35
36    //递归进行排序
37    private static <T extends Comparable<T>> void sort(T[] arr, int l, int r) {
38        if (l >= r)
39            return;
40        int mid = (r + l) / 2;
41        sort(arr, l, mid);
42        sort(arr, mid + 1, r);
43        merge(arr, l, mid, r);
44    }
45
46    //T需要实现Comparable接口,即T需为可排序的
47    public static <T extends Comparable<T>> void mergeSort(T[] arr) {
48        int n = arr.length;
49        sort(arr, 0, n - 1);
50    }
51
52    public static void main(String[] args) {
53        List<Integer> list = new ArrayList<>();
54        Collections.addAll(list, 2, 5, 6, 1, 7, 9, 3, 0);
55        //T[] toArray(T[] a):返回数组,返回数组的运行时类型与指定数组的运行时类型相同
56        Integer[] nums = list.toArray(new Integer[0]);
57        mergeSort(nums);
58        for (Integer num : nums) {
59            System.out.print(num + " ");
60        }
61    }
62} 

归并排序是稳定的。
时间复杂度:
  每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为log2n,总的平均时间复杂度为O(nlogn)。
空间复杂度:
  O(n)。

评论
发表评论
       
       
取消