排序之归并排序

归并排序

• 原理：
  • 建立在归并操作上的一种有效的排序算法
  • 将已有序的子序列合并，得到完全有序的序列
  • 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
• 归并排序是一个稳定的排序

实现方式

• 合并：是归并排序的核心操作

• 代码如下：

  private void merge(int[] array, int left, int mid, int right) {
              int i = left;
              int j = mid;
              int length = right - left;
              int[] extra = new int[length];
              int k = 0;
  
              while(i < mid && j < right) {
                      if(array[i] <= array[j]) {
                              extra[k++] = array[i++];
                      } else {
                              extra[k++] = array[j++];
                      }
              }
  
              while (i < mid) {
                      extra[k++] = array[i++];
              }
              while (j < right) {
                      extra[k++] = array[j++];
              }
  
              // 从 extra 搬移回 array
              for (int t = 0; t < length; t++) {
              // 需要搬移回原位置，从 low 开始
                      array[left + t] = extra[t];
              }
      }

• 递归实现操作：

  public void mergeSort(int[] array) {
      mergeSortInternal(array, 0, array.length);
  }
  
  private void mergeSortInternal(int[] array, int left, int right) {
      if(left >= right - 1)
          return;
  
      int mid = (left + right) >>> 1;
      mergeSortInternal(array, left, mid);
      mergeSortInternal(array, mid, right);
  
      merge(array, left, mid, right);
  }

• 非递归实现操作

  public void mergeSort(int[] array) {
              for (int i = 1; i < array.length; i = i * 2) {
                      for (int j = 0; j < array.length; j = j + 2 * i) {
                              int low = j;
                              int mid = j + i;
                              if (mid >= array.length) {
                                      continue;
                              }
                              int high = mid + i;
                              if (high > array.length) {
                                      high = array.length;
                              }
                              merge(array, low, mid, high);
                      }
              }
      }

性能分析

• 时间复杂度：O(N * log(N))
• 空间复杂度：O(N)
• 稳定性：稳定