Lwaxx的博客

十大排序算法（五） - 归并排序算法

发表于 更新于 分类于 ， 阅读次数： Valine：

归并排序（Merge Sort）是一种高效的、基于分治法的排序算法，它的稳定性和性能使其成为常用的排序方法之一。本文将详细介绍归并排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。

归并排序的基本思想

归并排序的核心思想是将数组分成两个子数组，递归地对这两个子数组进行排序，然后将它们合并成一个有序数组。这个过程分为以下几个步骤：

  1. 分割数组： 将待排序的数组分成两个子数组，通常是平均分割。这一步持续递归，直到每个子数组只包含一个元素。
  2. 递归排序： 递归地对左子数组和右子数组进行排序，直到它们都变成有序数组。
  3. 合并数组： 将已排序的左子数组和右子数组合并成一个有序数组。合并的过程中，逐个比较左右两个数组的元素，并将较小的元素添加到结果数组中，直到两个数组都为空。
  4. 返回结果： 最终得到一个完全排序好的数组。

归并排序的关键在于合并过程，也就是如何将两个有序数组合并成一个有序数组。这一过程保持了相等元素的相对顺序，因此归并排序是一种稳定的排序算法。

归并排序的示例

通过一个示例来理解归并排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。

  1. 分割数组： 首先将数组分成两个子数组 [5, 2] 和 [9, 3, 4]。
  2. 递归排序： 分别对左子数组 [5, 2] 和右子数组 [9, 3, 4] 递归地应用归并排序。
    • 对左子数组 [5, 2] 进行归并排序，得到 [2, 5]。
    • 对右子数组 [9, 3, 4] 进行归并排序，得到 [3, 4, 9]。
  3. 合并数组： 合并已排序的左子数组 [2, 5] 和右子数组 [3, 4, 9]。
    • 比较左右两个数组的首元素，选择较小的元素 2，将其添加到结果数组。
    • 继续比较，选择 3，将其添加到结果数组。
    • 接着选择 4、5、9，按顺序添加到结果数组。
  4. 返回结果： 最终，得到排序后的数组 [2, 3, 4, 5, 9]。

归并排序的时间复杂度

归并排序的时间复杂度非常稳定，始终为O(n*log(n))，其中n是数组的长度。这使得它适用于大型数据集和对稳定性有要求的情况。

尽管归并排序的时间复杂度相对较高，但它的性能稳定，对于各种数据集都表现出色。此外，归并排序是一种外部排序的重要算法，用于处理大型文件和数据库。

示例代码

以下是归并排序的示例代码，分别使用Python、Go、Java和C语言编写。

Python 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [5, 2, 9, 3, 4]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)

Go 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package main

import "fmt"

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := arr[:mid]
    right := arr[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)
}

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func main() {
    arr := []int{5, 2, 9, 3, 4}
    sorted_arr := mergeSort(arr)
    fmt.Println("排序后的数组:", sorted_arr)
}

Java 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = arr[mid + 1 + i];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

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

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

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 4};
        mergeSort(arr, 0, arr.length - 1);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}

C 语言 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArray[n1], rightArray[n2];

    for (int i = 0; i < n1; i++) {
        leftArray[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArray[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

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

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

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上示例代码展示了不同编程语言中的归并排序算法实现。这些示例帮助你理解归并排序的工作原理，并提供了可供参考和使用的代码示例。归并排序是一种稳定且高效的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。