转载

面试:归并排序和分治法

面试:归并排序和分治法

归并排序算法,时间复杂度 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];   }  }

2.2 效率

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为 O(N) ,故一共为 O(N*logN)

由于需要额外的数组来存储,空间复杂度是 O(N) .

在遇到相等的数据的时候必然是按顺序 抄写 到辅助数组上的,所以,归并排序同样是稳定算法。

因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

3 参考

  • 常见排序算法 - 归并排序 (Merge Sort)
正文到此结束
Loading...