0%

归并排序

发表于 更新于 分类于 Disqus：

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操

图示

递归法（Top-down）

基本思想

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

实现代码

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
public class SortUtil{
    
    // 递归版
    public static void merge_sort(int[] arr) {
        int len = arr.length;
        // 申请与原数组同等大小的数组
        int[] result = new int[len];
        merge_sort_recursive(arr, result, 0, len - 1);
    }
    static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    	if (start >= end)
    		return;
    	
    	// 将 一个数组 分为 2个 数组，递归分割，直到 得到的数组大小为1
    	int len = end - start, mid = (len >> 1) + start;
    	int start1 = start, end1 = mid;
    	int start2 = mid + 1, end2 = end;
    	merge_sort_recursive(arr, result, start1, end1);
    	merge_sort_recursive(arr, result, start2, end2);
    	
    	int k = start;
    	// 将 已排序的数组 依次取头部信息，比较大小，将小的数据，放入result中
    	// 比较 两个数组 头部数据的大小
    	while (start1 <= end1 && start2 <= end2)
    		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    	while (start1 <= end1)
    		result[k++] = arr[start1++];
    	while (start2 <= end2)
    		result[k++] = arr[start2++];
    	for (k = start; k <= end; k++)
    		arr[k] = result[k];
    }
}

迭代法（Bottom-up）

基本思想

原理如下（假设序列共有 n 个元素）：

  1. 将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素
  2. 若此时序列数不是1个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素
  3. 重复步骤2，直到所有元素排序完毕，即序列数为1

代码实现

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

public class SortUtil{
    
    
    //迭代版
    public static void mergeSort(int[] arr) {
      int[] orderedArr = new int[arr.length];
            for (int i = 2; i < arr.length * 2; i *= 2) {
                for (int j = 0; j < (arr.length + i - 1) / i; j++) {
                    int left = i * j;
                    int mid = left + i / 2 >= arr.length ? (arr.length - 1) : (left + i / 2);
                    int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1);
                    int start = left, l = left, m = mid;
                    while (l < mid && m <= right) {
                        if (arr[l] < arr[m]) {
                            orderedArr[start++] = arr[l++];
                        } else {
                            orderedArr[start++] = arr[m++];
                        }
                    }
                    while (l < mid)
                        orderedArr[start++] = arr[l++];
                    while (m <= right)
                        orderedArr[start++] = arr[m++];
                    System.arraycopy(orderedArr, left, arr, left, right - left + 1);
                }
            } 
    }
}

参考

图解-归并
wiki