跳到主要内容

归并排序算法

提示
  1. 归并排序原理：基于分治算法的排序方法，将问题分解为子问题，独立解决并合并结果。
  2. 分治策略实现：将数组分为两部分，分别排序后合并，重复此过程直到整个数组排序完成。
  3. 效率和应用：时间复杂度为 O(n*log n)，适用于逆序数问题、外部排序和电子商务应用。

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

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

归并排序示例

分治策略​

使用分治技术，我们将一个问题分解为子问题。当每个子问题的解决方案准备就绪时，我们会将子问题的结果'合并'起来以解决主问题。

假设我们需要对数组 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..q] 和 A[q+1, r] 用于数组 A[p..r] 时，我们通过创建一个已排序的数组 A[p..r] 来合并结果。

归并排序算法​

MergeSort 函数重复地将数组分成两半，直到我们尝试在大小为1的子数组上执行 MergeSort，即 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个元素的数组的基本情况。然后，合并函数将已排序的子数组取出并逐渐排序整个数组。

归并排序算法可视化

归并排序的合并步骤​

每个递归算法都依赖于基本情况和组合基本情况结果的能力。归并排序也不例外。归并排序算法中最重要的部分是合并步骤。

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

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

已经到达了任一数组的末尾吗？
    否：
        比较两个数组的当前元素
        将较小的元素复制到已排序数组中
        移动包含较小元素的元素的指针
    是：
        复制非空数组的所有剩余元素

合并两个已排序的数组

编写合并算法的代码​

我们上面描述的合并步骤和我们用于归并排序的合并步骤之间的一个显着差异是，我们仅对连续的子数组执行合并函数。

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

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

合并函数的工作方式如下：

  1. 创建子数组的副本 L <- A[p..q] 和 M <- A[q+1..r]。

  2. 创建三个指针 i、j 和 k。

  3. i 维护 L 的当前索引，从1开始。

  4. j 维护 M 的当前索引，从1开始。

  5. k 维护 A[p..q] 的当前索引，从 p 开始。

直到 L 或 M 中的一个结束，选择 L 和 M 中元素中的较大者，并将它们放在 A[p..q] 的正确位置上。

当我们耗尽 L 或 M 中的元素时，将剩余元素拾起并放入 A[p..q]。

在代码中，这将如下所示：

// 合并两个子数组 L 和 M 到 arr
void merge(int arr[], int p, int q, int r) {

    // 创建 L ← A[p..q] 和 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];

    // 维护子数组和主数组的当前索引
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // 直到我们到达 L 或 M 的末尾之一，选择 L 和 M 中元素中较大的一个，并将它们放在 A[p..q] 的正确位置上
    // 当我们耗尽 L 或 M 中的元素时，拾起剩余的元素并放入 A[p..q]
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

逐步解释 Merge( ) 函数​

这个函数里面发生了很多事情，让我们通过一个例子来看看它是如何工作的。

像往常一样，图片胜过千言万语。

合并数组的两个连续子数组

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

void merge(int arr[], int p, int q, int r) {
// 这里，p = 0, q = 4, r = 6（数组大小）

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

    // 创建 L ← A[p..q] 和 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]

创建要合并的子数组的副本

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


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

维护子数组和主数组的副本的索引

步骤 3：直到我们到达 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++;
    }

比较已排序子数组的单个元素，直到我们达到其中一个的末尾

步骤 4：当我们在 L 或 M 中的一个元素用完时，取出剩余的元素并放入 A[p..r]​

    // 之前的循环退出是因为 j < n2 不成立
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

将第一个数组中的剩余元素复制到主子数组

    // 之前的循环退出是因为 i < n1 不成立
    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}

将第二个数组中的剩余元素复制到主子数组

如果 M 的大小大于 L，将需要执行此步骤。

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

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

Python Java C

# 在 Python 中的归并排序


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

        #  r 是数组分为两个子数组的位置
        r = len(array)//2
        L = array[:r]
        M = array[r:]

        # 对两半进行排序
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        # 直到我们到达 L 或 M 的末尾之一，选择较大的元素并将它们放在 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

        # 当我们在 L 或 M 中的一个元素用完时，取出剩余的元素并放入 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


# 打印数组
def printList(array):
    for i in range(len(array)):
        print(array[i], end=" ")
    print()


# 主程序
if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]

    mergeSort(array)

    print("排序后的数组是: ")
    printList(array)
// Java 中的归并排序

class MergeSort {

  // 合并两个子数组 L 和 M 到 arr
  void merge(int arr[], int p, int q, int r) {

    // 创建 L ← A[p..q] 和 M ← A[q+1..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];

    // 维护子数组和主数组的当前索引
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // 直到我们到达 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++;
    }

    // 当我们在 L 或 M 中的一个元素用完时，取出剩余的元素并放入 A[p..r]
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

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

  // 将数组分为两个子数组，对它们进行排序并合并它们
  void mergeSort(int arr[], int l, int r) {
    if (l < r) {

      // m 是数组分为两个子数组的位置
      int m = (l + r) / 2;

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

      // 合并已排序的子数组
      merge(arr, l, m, r);
    }
  }

  // 打印数组
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  // 主程序
  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("已排序数组:");
    printArray(arr);
  }
}

归并排序算法在 C 和 C++ 中的实现​

// C 中的归并排序

#include <stdio.h>

// 合并两个子数组 L 和 M 到 arr
void merge(int arr[], int p, int q, int r) {

  // 创建 L ← A[p..q] 和 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];

  // 维护子数组和主数组的当前索引
  int i, j, k;
  i = 0;
  j = 0;
  k = p;

  // 直到达到 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++;
  }

  // 当 L 或 M 的元素用尽时，
  // 拿起剩下的元素并放在 A[p..r]
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

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

// 将数组分成两个子数组，排序它们并合并
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    // m 是数组被分成两个子数组的点
    int m = l + (r - l) / 2;

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

    // 合并已排序的子数组
    merge(arr, l, m, r);
  }
}

// 打印数组
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// 驱动程序
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);
}
// C++ 中的归并排序

#include <iostream>
using namespace std;

// 合并两个子数组 L 和 M 到 arr
void merge(int arr[], int p, int q, int r) {

  // 创建 L ← A[p..q] 和 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];

  // 维护子数组和主数组的当前索引
  int i, j, k;
  i = 0;
  j = 0;
  k = p;

  // 直到达到 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++;
  }

  // 当 L 或 M 的元素用尽时，
  // 拿起剩下的元素并放在 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)。

归并排序应用​

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

类似的排序算法​

  1. 快速排序
  2. 插入排序
  3. 选择排序
  4. 桶排序
最后于 更新