归并排序与堆排序：复杂度分析及Java实现

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。递归形式的算法在形式上较简洁，但实用性很差。一般情况下，很少利用二路归并排序法进行内部排序。 归并排序是一种基于分治策略的排序算法，其基本思想是将待排序的序列分成两个或更多的子序列，分别对这些子序列进行排序，然后将排序好的子序列合并成一个完整的有序序列。这个过程可以递归地进行，直到每个子序列只包含一个元素，此时再逐一合并这些单元素序列。 在归并排序中，最重要的是“归并”操作。当两个已排序的子序列需要合并时，我们需要创建一个临时数组，用于存储合并后的新序列。我们用两个指针分别指向两个子序列的起始位置，比较这两个指针所指向的元素，将较小的元素放入临时数组，并将对应的指针向后移动一位。这个过程持续进行，直到其中一个子序列的所有元素都被放入临时数组。接着，我们将另一个子序列的剩余元素直接复制到临时数组的末尾，完成一次归并操作。 Java中实现归并排序通常包括以下步骤： 1. 定义一个方法`sort()`，接受一个整型数组、起始下标`low`和结束下标`high`作为参数。如果`low`小于`high`，则说明数组还需要继续分割。 2. 计算中间下标`mid`，将数组分成左右两部分，分别对左右部分递归调用`sort()`方法。 3. 在每次递归返回后，调用`merge()`方法，将左右两个已排序的部分合并。 4. `merge()`方法创建一个与原数组长度相等的临时数组`temp`，通过两个指针`i`和`j`分别跟踪左右子序列，将较小的元素依次放入`temp`，直到其中一个子序列遍历完。将另一个子序列剩余的元素复制到`temp`的剩余位置。 以下是一个简单的Java归并排序代码示例： ```java public class MergeSort { public static void main(String[] args) { int[] array = {3, 5, 2, 6, 2}; array = sort(array, 0, array.length - 1); for (int num : array) { System.out.print(num + " "); } } private static int[] sort(int[] array, int low, int high) { if (low < high) { int mid = (low + high) / 2; sort(array, low, mid); sort(array, mid + 1, high); merge(array, low, mid, high); } return array; } private static void merge(int[] array, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } while (i <= mid) { temp[k++] = array[i++]; } while (j <= high) { temp[k++] = array[j++]; } System.arraycopy(temp, 0, array, low, temp.length); } } ``` 这段代码首先定义了一个`sort()`方法，将数组按中间位置分割，然后对左右子序列进行递归调用。`merge()`方法负责合并两个已排序的子序列。`main()`方法中创建了一个示例数组，并调用`sort()`方法进行排序，然后打印出排序后的结果。 需要注意的是，虽然归并排序的时间复杂度为O(n log n)，但在空间复杂度上较高，因为它需要额外的内存空间来存储合并过程中的临时数组。因此，在处理大量数据且内存资源有限的情况下，可能会选择其他排序算法，如快速排序或堆排序。然而，归并排序由于其稳定性，常被用在外部排序和其他需要稳定性的场景。