转载

面试：归并排序和分治法

归并排序算法，时间复杂度 O(NlogN) ，空间复杂度 O(N) 。

分治法（Divide and Conquer）的一个非常典型的应用。

参考链表的归并，模板代码： Merge K Sorted Lists--leetcode

1.如何将2个有序数列合并

简单，只要比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

合并有序数列的效率是比较高的，可以达到 O(n) 。

    // 合并两个有序的数组a和b,合并的结果放在数组c中;  // 1. i,j,k表示数组a,b,c的下标  // 2. 每次取a,b中小的数放在c中  // 3. 收尾工作  public void merge(int[] a, int[] b, int[] c) {   int i = 0, j = 0, k = 0;   while (i <= a.length && j <= b.length) {    if (a[i] <= b[i]) {     c[k++] = a[i++];    } else {     c[k++] = b[j++];    }   }   while (i <= a.length) {    c[k++] = a[i++];   }   while (j <= b.length) {    c[k++] = b[j++];   }  }

2.归并排序

基于1，归并排序的基本思路就是将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。

2.1 如何让这2组组内数据有序了？

可以将A，B组各自再分成2组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

归并的2个步骤： mergeSort

1.将数组A不断的划分成左右2个数组，直到每个数组都只有1个数据 internalMergeSort
2.合并两个有序的数组 mergeSortedArray

    // 归并排序  public void mergeSort(int[] arr) {   int[] temp = new int[arr.length];   internalMergeSort(arr, temp, 0, arr.length - 1);  }   private void internalMergeSort(int[] a, int[] temp, int left, int right) {   // 当left==right的时，已经不需要再划分了   if (left < right) {    int middle = (left + right) / 2;    internalMergeSort(a, temp, left, middle); // 左子数组    internalMergeSort(a, temp, middle + 1, right); // 右子数组    mergeSortedArray(a, temp, left, middle, right); // 合并两个子数组   }  }   // 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。  private void mergeSortedArray(int arr[], int temp[], int left,    int middle, int right) {   int i = left;   int j = middle + 1;   int k = 0;   while (i <= middle && j <= right) {    if (arr[i] <= arr[j]) {     temp[k++] = arr[i++];    } else {     temp[k++] = arr[j++];    }   }   while (i <= middle) {    temp[k++] = arr[i++];   }   while (j <= right) {    temp[k++] = arr[j++];   }   // 把数据复制回原数组   for (i = 0; i < k; i++) {    arr[left + i] = temp[i];   }  }