数据结构第21节 归并排序以及优化方案

归并排序（Merge Sort）是一种分治策略的排序算法。它将一个大数组分成两个子数组，递归地对它们进行排序，然后将排序后的子数组合并成一个有序数组。

Java代码实现：

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {5, 2, 8, 3, 1, 6, 9, 7, 4};
        mergeSort(array, 0, array.length - 1);
        
        // 打印排序后的数组
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            // 递归调用归并排序函数，对左边子数组进行排序
            mergeSort(array, left, middle);

            // 递归调用归并排序函数，对右边子数组进行排序
            mergeSort(array, middle + 1, right);

            // 合并两个子数组
            merge(array, left, middle, right);
        }
    }

    private static void merge(int[] array, int left, int middle, int right) {
        int n1 = middle - left + 1; // 左子数组长度
        int n2 = right - middle;    // 右子数组长度

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 复制数据到临时数组中
        for (int i = 0; i < n1; ++i)
            L[i] = array[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = array[middle + 1 + j];

        // 合并临时数组回原数组
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k] = L[i];
                i++;
            } else {
                array[k] = R[j];
                j++;
            }
            k++;
        }

        // 拷贝剩余元素
        while (i < n1) {
            array[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = R[j];
            j++;
            k++;
        }
    }
}

这个程序首先定义了一个mergeSort方法来执行排序操作。它接收数组和左右边界作为参数。如果左边界小于右边界，它会计算中间点，并递归地对左侧和右侧的子数组进行排序，最后调用merge方法来合并这两个子数组。

merge方法创建了两个临时数组来存储分割后的子数组，然后比较这两个子数组中的元素，并按顺序将较小的元素放回原始数组中，直到其中一个子数组的元素被全部放入原始数组。最后，如果有任何剩余的元素，它们会被复制到原始数组中。

整个过程重复进行，直到所有子数组都被排序并合并回原始数组，从而得到完全排序的数组。

在归并排序中，我们可以做一些小的改进来优化性能或者代码的可读性。以下是一些可能的优化点：

1. 避免重复计算：在mergeSort函数中，每次递归调用都会计算中间点。我们可以在主函数中预先计算中间点，减少重复计算。

2. 使用非递归版本：虽然递归实现简洁，但是过多的递归调用可能会导致栈溢出。可以使用迭代的方式来实现归并排序，使用循环和栈或队列等数据结构。

3. 优化合并过程：在合并时，可以尝试减少数组的复制次数，比如使用索引直接在原数组上进行操作。

4. 使用哨兵值：在合并阶段，可以通过设置哨兵值来简化边界条件的处理。

下面是基于上述优化点之一，即使用非递归版本的归并排序实现：

public class MergeSortNonRecursive {

    public static void main(String[] args) {
        int[] array = {5, 2, 8, 3, 1, 6, 9, 7, 4};
        mergeSortNonRecursive(array);
        
        // 打印排序后的数组
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public static void mergeSortNonRecursive(int[] array) {
        int n = array.length;
        int[] temp = new int[n]; // 用于合并操作的临时数组

        // 初始步长为1，每次翻倍
        for (int step = 1; step < n; step *= 2) {
            // 从头开始，每次步长移动
            for (int leftStart = 0; leftStart < n - step; leftStart += 2 * step) {
                int mid = leftStart + step - 1;
                int rightEnd = Math.min(leftStart + 2 * step - 1, n - 1);
                merge(array, leftStart, mid, rightEnd, temp);
            }
        }
    }

    private static void merge(int[] array, int leftStart, int mid, int rightEnd, int[] temp) {
        int leftEnd = mid;
        int rightStart = mid + 1;
        int left = leftStart;
        int right = rightStart;
        int index = leftStart;

        // 合并过程
        while (left <= leftEnd && right <= rightEnd) {
            if (array[left] <= array[right]) {
                temp[index++] = array[left++];
            } else {
                temp[index++] = array[right++];
            }
        }

        // 拷贝剩余的元素
        while (left <= leftEnd) {
            temp[index++] = array[left++];
        }
        while (right <= rightEnd) {
            temp[index++] = array[right++];
        }

        // 将排序结果复制回原数组
        for (int i = leftStart; i <= rightEnd; i++) {
            array[i] = temp[i];
        }
    }
}

在这个版本中，我们使用了一个循环来控制步长的增长，从1开始，每次翻倍，直到步长大于或等于数组的长度。在每次循环中，我们将数组按照当前步长分割成多个子数组对，并对每一对子数组进行合并操作。这样就避免了递归带来的潜在问题，同时也保持了归并排序的时间复杂度O(n log n)。

对于归并排序，进一步的优化通常集中在减少内存使用、提高缓存效率以及避免不必要的数据复制等方面。以下是一个更优化的归并排序实现，主要改进点在于：

1. 减少额外空间：通常归并排序需要与输入数组相同大小的辅助数组，这里我们通过调整合并策略来减少所需的空间。

2. 提高缓存局部性：通过调整合并的方式，让数据访问模式更加连续，从而提高CPU缓存的命中率。

3. 微优化：在合并过程中，通过避免不必要的边界检查和条件判断，提高执行效率。

以下是结合这些优化点的归并排序Java代码：

public class OptimizedMergeSort {

    public static void main(String[] args) {
        int[] array = {5, 2, 8, 3, 1, 6, 9, 7, 4};
        optimizedMergeSort(array);
        
        // 打印排序后的数组
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public static void optimizedMergeSort(int[] array) {
        int n = array.length;
        int[] aux = new int[n/2]; // 辅助数组，大小为输入数组的一半

        // 自底向上迭代归并排序
        for (int sz = 1; sz < n; sz *= 2) {
            for (int lo = 0; lo < n - sz; lo += sz * 2) {
                int mid = lo + sz - 1;
                int hi = Math.min(lo + sz * 2 - 1, n - 1);
                merge(array, lo, mid, hi, aux);
            }
        }
    }

    private static void merge(int[] array, int lo, int mid, int hi, int[] aux) {
        // 使用辅助数组进行合并
        int auxLo = lo;
        int auxHi = mid + 1;
        int k = lo;

        // 如果辅助数组空间不足，则直接使用原数组的一部分
        if (auxHi - auxLo > aux.length) {
            System.arraycopy(array, auxLo, aux, 0, auxHi - auxLo);
            auxLo = 0;
            auxHi -= auxLo;
        } else {
            System.arraycopy(array, auxLo, aux, auxLo, auxHi - auxLo);
        }

        while (auxLo <= mid - lo && auxHi <= hi) {
            if (aux[auxLo] <= array[auxHi]) {
                array[k++] = aux[auxLo++];
            } else {
                array[k++] = array[auxHi++];
            }
        }

        // 剩余部分拷贝回原数组
        while (auxLo <= mid - lo) {
            array[k++] = aux[auxLo++];
        }
        while (auxHi <= hi) {
            array[k++] = array[auxHi++];
        }
    }
}

在这个版本中，我们使用了一个大小仅为原数组一半的辅助数组aux。当合并操作涉及的数据量超过aux的容量时，我们会直接在原数组中进行操作，而不是使用额外的辅助空间。这减少了所需的辅助空间，但同时也增加了算法的复杂性，因为需要更仔细地管理原数组和辅助数组之间的数据交换。

请注意，这种优化可能会增加代码的复杂性和难度，而且在某些情况下，由于现代处理器的高速缓存机制，使用较大的辅助数组可能反而能提供更好的性能。因此，在实际应用中，需要根据具体情况和目标平台来权衡是否采用这样的优化。

将上述优化后的归并排序代码以表格形式展示，可以帮助理解代码的结构和流程。下面是对代码逻辑的分解，以表格形式呈现：

这个表格展示了代码的主要结构和每个部分的功能，有助于理解优化后的归并排序算法是如何工作的。注意，表格中的描述是简化的，实际代码中可能包含更多的细节和边界条件的处理。

为了更好地说明优化后的归并排序的过程，我们可以将整个排序过程分解成几个关键步骤，并用表格形式表示。这里以数组 [5, 2, 8, 3, 1, 6, 9, 7, 4] 为例，展示整个排序过程。

初始状态：

Array: [5, 2, 8, 3, 1, 6, 9, 7, 4]

过程分析：

第一阶段：分割数组

• Step 1: 以步长为1开始，分割数组为单个元素。
• Step 2: 合并相邻的单个元素，形成有序对。
• Step 3: 以步长为2，分割数组为有序对。
• Step 4: 合并相邻的有序对，形成更长的有序序列。
• …
• Step N: 重复此过程，直到整个数组被排序。

第二阶段：合并数组

• Merge 1: 合并 [5, 2] 和 [8, 3] 成为 [2, 5, 3, 8]。
• Merge 2: 合并 [1, 6] 和 [9, 7] 成为 [1, 6, 7, 9]。
• Merge 3: 合并 [4] 单独存在。
• Merge 4: 合并 [2, 5, 3, 8] 和 [1, 6, 7, 9] 成为 [1, 2, 3, 5, 6, 7, 8, 9]。
• Merge 5: 最后合并 [1, 2, 3, 5, 6, 7, 8, 9] 和 [4] 成为最终的有序数组。

归并排序过程解析：

请注意，实际的归并排序过程中，数组的“分割”并不是物理上的分割，而是逻辑上的分割，即在算法的控制下分别处理数组的不同部分。合并操作则是在原地进行的，利用辅助数组或特定的算法技巧，将两个有序子数组合并成一个更大的有序子数组。

以上表格提供了一种简化的方式来理解归并排序的各个阶段，但实际上每一次合并操作都涉及到复杂的元素比较和重排。