归并排序算法¶

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分割数组
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 递归排序两半
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 合并两个已排序的半数组
    return merge(left_half, right_half)

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, 3, 8, 4, 2]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        int[] sorted = mergeSort(arr);
        System.out.println("排序后的数组:");
        for (int num : sorted) {
            System.out.print(num + " ");
        }
    }

    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }

        // 分割数组
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        // 递归排序两半
        left = mergeSort(left);
        right = mergeSort(right);

        // 合并两个已排序的半数组
        return merge(left, right);
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        // 比较两个数组的元素并合并
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        // 添加剩余元素
        while (i < left.length) {
            result[k++] = left[i++];
        }

        while (j < right.length) {
            result[k++] = right[j++];
        }

        return result;
    }
}