归并排序算法

归并排序是基于分治算法原理的最流行的排序算法之一。

在这里，一个问题被分解成多个子问题。每个子问题都会被单独解决。最后，将子问题合并形成最终的解决方案。

分治策略

使用分治技术，我们将问题分解为子问题。当每个子问题的解决方案准备就绪后，我们“合并”子问题的结果来解决主问题。

假设我们要对数组 A 进行排序。子问题将是对该数组从索引 p 开始到索引 r 结束的子部分进行排序，记为 A[p..r]。

除法

如果 q 是 p 和 r 之间的中间点，那么我们可以将子数组 A[p..r] 分为两个数组 A[p..q] 和 A[q+1, r]。

征服

在征服步骤中，我们尝试对两个子数组 A[p..q] 和 A[q+1, r] 进行排序。如果我们还没有到达基本情况，我们再次将这两个子数组进行划分并尝试排序。

合并

当征服步骤到达基本情况，并且我们得到了数组 A[p..r] 的两个已排序子数组 A[p..q] 和 A[q+1, r] 时，我们通过从两个已排序子数组 A[p..q] 和 A[q+1, r] 创建一个已排序数组 A[p..r] 来合并结果。

归并排序算法

归并排序函数反复将数组分成两半，直到我们到达尝试对大小为 1 的子数组执行归并排序的阶段，即 p == r。

之后，合并函数发挥作用，将已排序的数组合并成更大的数组，直到整个数组被合并。

MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

要对整个数组进行排序，我们需要调用 MergeSort(A, 0, length(A)-1)。

如下图所示，归并排序算法递归地将数组分成两半，直到我们到达具有 1 个元素的数组的基本情况。之后，合并函数拾取已排序的子数组，并将它们合并，逐渐对整个数组进行排序。

merge sort algorithm visualization — 归并排序实操

归并排序的合并步骤

每个递归算法都依赖于一个基本情况以及合并来自基本情况结果的能力。归并排序也不例外。归并排序算法最重要的部分是，你猜对了，merge 步骤。

合并步骤是解决将两个已排序列表（数组）合并以构建一个大的已排序列表（数组）的简单问题的方案。

该算法维护三个指针，一个指向两个数组中的每个数组，一个用于维护已排序的最终数组的当前索引。

Have we reached the end of any of the arrays?
    No:
        Compare current elements of both arrays 
        Copy smaller element into sorted array
        Move pointer of element containing smaller element
    Yes:
        Copy all remaining elements of non-empty array

编写归并算法代码

我们上面描述的合并步骤与我们用于归并排序的合并步骤之间的一个显著区别是，我们只对连续的子数组执行合并函数。

这就是为什么我们只需要数组、第一个位置、第一个子数组的最后一个索引（我们可以计算第二个子数组的第一个索引）和第二个子数组的最后一个索引。

我们的任务是将两个子数组 A[p..q] 和 A[q+1..r] 合并以创建已排序数组 A[p..r]。因此，函数的输入是 A、p、q 和 r。

合并函数工作如下：

创建子数组的副本 L <- A[p..q] 和 M <- A[q+1..r]。
创建三个指针 i、j 和 k。
1. i 维护 L 的当前索引，从 1 开始。
2. j 维护 M 的当前索引，从 1 开始。
3. k 维护 A[p..q] 的当前索引，从 p 开始。
在 L 或 M 的末尾之前，从 L 和 M 中选择较大的元素，并将它们放置在 A[p..q] 的正确位置。
当 L 或 M 中的元素耗尽时，拾取剩余的元素并放入 A[p..q]。

在代码中，这看起来是这样的：

// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {

    // Create L ← A[p..q] and M ← A[q+1..r]
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1], M[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}

Merge() 函数分步解释

这个函数里有很多操作，所以我们用一个例子来看看它是如何工作的。

一如既往，一张图片胜过千言万语。

Merging two consecutive subarrays of array — 合并数组的两个连续子数组

数组 A[0..5] 包含两个已排序的子数组 A[0..3] 和 A[4..5]。让我们看看合并函数将如何合并这两个数组。

void merge(int arr[], int p, int q, int r) {
// Here, p = 0, q = 4, r = 6 (size of array)

步骤 1：创建要排序的子数组的副本

    // Create L ← A[p..q] and M ← A[q+1..r]
    int n1 = q - p + 1 = 3 - 0 + 1 = 4;
    int n2 = r - q = 5 - 3 = 2;

    int L[4], M[2];

    for (int i = 0; i < 4; i++)
        L[i] = arr[p + i];
        // L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

    for (int j = 0; j < 2; j++)
        M[j] = arr[q + 1 + j];
        // M[0,1] = A[4,5] = [6,9]

Create copies of subarrays for merging — 创建要合并的子数组副本

步骤 2：维护子数组和主数组的当前索引

    
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p;

Maintain indices of copies of sub array and main array — 维护子数组副本和主数组的索引

步骤 3：在 `L` 或 `M` 的末尾之前，选择 `L` 和 `M` 中较大的元素，并将它们放置在 `A[p..r]` 的正确位置。

    while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            arr[k] = L[i]; i++; 
        } 
        else { 
            arr[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

Comparing individual elements of sorted subarrays until we reach end of one — 比较已排序子数组的单个元素，直到到达其中一个的末尾

步骤 4：当 `L` 或 `M` 中的元素耗尽时，拾取剩余的元素并放入 `A[p..r]`。

    // We exited the earlier loop because j < n2 doesn't hold
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

Copy the remaining elements from the first array to main subarray — 将第一个数组的剩余元素复制到主子数组

    // We exited the earlier loop because i < n1 doesn't hold  
    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}

Copy remaining elements of second array to main subarray — 将第二个数组的剩余元素复制到主子数组

如果 M 的大小大于 L，则需要此步骤。

在合并函数结束时，子数组 A[p..r] 已排序。

Python、Java 和 C/C++ 中的归并排序代码

归并排序可视化：不要只阅读归并排序，观看它实时发生。通过我们新的 DSA 可视化工具，了解算法的每一行如何逐步工作。亲自尝试！

Python

Java

C++

# MergeSort in Python


def mergeSort(array):
    if len(array) > 1:

        #  r is the point where the array is divided into two subarrays
        r = len(array)//2
        L = array[:r]
        M = array[r:]

        # Sort the two halves
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        # Until we reach either end of either L or M, pick larger among
        # elements L and M and place them in the correct position at A[p..r]
        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1

        # When we run out of elements in either L or M,
        # pick up the remaining elements and put in A[p..r]
        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1


# Print the array
def printList(array):
    for i in range(len(array)):
        print(array[i], end=" ")
    print()


# Driver program
if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]

    mergeSort(array)

    print("Sorted array is: ")
    printList(array)

// Merge sort in Java

class MergeSort {

  // Merge two subarrays L and M into arr
  void merge(int arr[], int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int M[] = new int[n2];

    for (int i = 0; i < n1; i++)
      L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
      M[j] = arr[q + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = M[j];
        j++;
      }
      k++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k] = M[j];
      j++;
      k++;
    }
  }

  // Divide the array into two subarrays, sort them and merge them
  void mergeSort(int arr[], int l, int r) {
    if (l < r) {

      // m is the point where the array is divided into two subarrays
      int m = (l + r) / 2;

      mergeSort(arr, l, m);
      mergeSort(arr, m + 1, r);

      // Merge the sorted subarrays
      merge(arr, l, m, r);
    }
  }

  // Print the array
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  // Driver program
  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort ob = new MergeSort();
    ob.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array:");
    printArray(arr);
  }
}

// Merge sort in C

#include <stdio.h>

// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {

  // Create L ← A[p..q] and M ← A[q+1..r]
  int n1 = q - p + 1;
  int n2 = r - q;

  int L[n1], M[n2];

  for (int i = 0; i < n1; i++)
    L[i] = arr[p + i];
  for (int j = 0; j < n2; j++)
    M[j] = arr[q + 1 + j];

  // Maintain current index of sub-arrays and main array
  int i, j, k;
  i = 0;
  j = 0;
  k = p;

  // Until we reach either end of either L or M, pick larger among
  // elements L and M and place them in the correct position at A[p..r]
  while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  // When we run out of elements in either L or M,
  // pick up the remaining elements and put in A[p..r]
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = M[j];
    j++;
    k++;
  }
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
  if (l < r) {

    // m is the point where the array is divided into two subarrays
    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    // Merge the sorted subarrays
    merge(arr, l, m, r);
  }
}

// Print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// Driver program
int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, size - 1);

  printf("Sorted array: \n");
  printArray(arr, size);
}

// Merge sort in C++
#include <iostream>
#include <vector>
using namespace std;

// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
  
  // Create L ← A[p..q] and M ← A[q+1..r]
  int n1 = q - p + 1;
  int n2 = r - q;
  
  // Use std::vector to dynamically allocate arrays
  vector<int> L(n1);
  vector<int> M(n2);
  
  for (int i = 0; i < n1; i++)
    L[i] = arr[p + i];
    
  for (int j = 0; j < n2; j++)
    M[j] = arr[q + 1 + j];
    
  // Maintain current index of sub-arrays and main array
  int i = 0, j = 0, k = p;
  
  // Until we reach either end of either L or M, pick larger among
  // elements L and M and place them in the correct position at A[p..r]
  while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = M[j];
      j++;
    }
    k++;
  }
  
  // When we run out of elements in either L or M,
  // pick up the remaining elements and put in A[p..r]
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  
  while (j < n2) {
    arr[k] = M[j];
    j++;
    k++;
  }
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    // m is the point where the array is divided into two subarrays
    int m = l + (r - l) / 2;
    
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    // Merge the sorted subarrays
    merge(arr, l, m, r);
  }
}

// Print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

// Driver program
int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, size - 1);
  cout << "Sorted array: \n";
  printArray(arr, size);
  return 0;
}

归并排序复杂度

时间复杂度
最佳	O(n*log n)
最坏	O(n*log n)
平均	O(n*log n)
空间复杂度	O(n)
稳定性	是

时间复杂度

最佳情况复杂度：O(n*log n)

最坏情况复杂度：O(n*log n)

平均情况复杂度：O(n*log n)

空间复杂度

归并排序的空间复杂度为 O(n)。

归并排序的应用

逆序对问题
外部排序
电子商务应用

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python
程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

归并排序算法

分治策略

归并排序算法

归并排序的合并步骤

编写归并算法代码

Merge() 函数分步解释

步骤 1：创建要排序的子数组的副本

步骤 2：维护子数组和主数组的当前索引

步骤 3：在 `L` 或 `M` 的末尾之前，选择 `L` 和 `M` 中较大的元素，并将它们放置在 `A[p..r]` 的正确位置。

步骤 4：当 `L` 或 `M` 中的元素耗尽时，拾取剩余的元素并放入 `A[p..r]`。

Python、Java 和 C/C++ 中的归并排序代码

归并排序复杂度

时间复杂度

空间复杂度

归并排序的应用

类似的排序算法

目录

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

DSA 教程

归并排序算法

分治策略

归并排序算法

归并排序的合并步骤

编写归并算法代码

Merge() 函数分步解释

步骤 1：创建要排序的子数组的副本

步骤 2：维护子数组和主数组的当前索引

步骤 3：在 L 或 M 的末尾之前，选择 L 和 M 中较大的元素，并将它们放置在 A[p..r] 的正确位置。

步骤 4：当 L 或 M 中的元素耗尽时，拾取剩余的元素并放入 A[p..r]。

Python、Java 和 C/C++ 中的归并排序代码

归并排序复杂度

时间复杂度

空间复杂度

归并排序的应用

类似的排序算法

目录

相关教程

成为一名认证的 Python
程序员。

步骤 3：在 `L` 或 `M` 的末尾之前，选择 `L` 和 `M` 中较大的元素，并将它们放置在 `A[p..r]` 的正确位置。

步骤 4：当 `L` 或 `M` 中的元素耗尽时，拾取剩余的元素并放入 `A[p..r]`。