java归并排序

归并排序(Merge Sort)是一种基于分治策略的排序算法。其基本思想是将一个大问题分解成小问题，然后递归求解，最后将小问题的解合并成大问题的解。归并排序是稳定的排序算法，并且具有较好的时间复杂度，通常为 O(n log n)。

以下是归并排序的基本步骤和Java代码实现：

基本步骤

  1. 分解 ：将待排序序列分成两个子序列，直到每个子序列只有一个元素。

  2. 递归 ：递归地对每个子序列进行排序。

  3. 合并 ：将两个已排序的子序列合并成一个有序序列。

Java代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {45, 4, 56, 3}；
        mergeSort(array, 0, array.length - 1)；
        System.out.println(Arrays.toString(array))；
    }

    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2；
            mergeSort(array, left, mid)；
            mergeSort(array, mid + 1, right)；
            merge(array, left, mid, right)；
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int[] tempArray = new int[right - left + 1]；
        int i = left, j = mid + 1, k = 0；

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                tempArray[k++] = array[i++]；
            } else {
                tempArray[k++] = array[j++]；
            }
        }

        while (i <= mid) {
            tempArray[k++] = array[i++]；
        }

        while (j <= right) {
            tempArray[k++] = array[j++]；
        }

        System.arraycopy(tempArray, 0, array, left, tempArray.length)；
    }
}

解释

  • mergeSort 方法是递归的，它将数组分成两部分，然后对每部分进行排序，最后合并排序好的两部分。

  • merge 方法负责合并两个已排序的子数组，创建一个临时数组来存储合并后的结果，并复制回原数组。

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。由于其稳定的特性和高效的性能，归并排序在许多场合都是首选的排序算法之一

Top
×
×