给出使用归并排序的

### 归并排序算法的实现与使用 #### Java 实现归并排序 归并排序是一种分治法的应用，它通过递归的方式将数组分成更小的部分，再逐步合并这些部分来完成排序。以下是基于 Java 的归并排序实现： ```java public class MergeSort { public static void main(String[] args) { int[] array = {4, 5, 3, 3, 1, 2, 2, 4}; mergeSort(array, 0, array.length - 1); System.out.print("排序后的数组："); for (int num : array) { System.out.print(num + " "); } } 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 n1 = mid - left + 1; // 左半部分长度 int n2 = right - mid; // 右半部分长度 /* 创建临时数组 */ 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[mid + 1 + j]; /* 合并临时数组到原数组 */ int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k++] = L[i++]; } else { array[k++] = R[j++]; } } /* 复制剩余元素 */ while (i < n1) array[k++] = L[i++]; while (j < n2) array[k++] = R[j++]; } } ``` 此代码展示了如何利用 `merge` 和 `mergeSort` 方法对数组进行分割和合并操作[^4]。 --- #### Python 实现归并排序 Python 提供了一种简洁的方式来实现归并排序。下面是一个完整的例子： ```python def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 # 找到中间位置 left_half = arr[:mid] # 划分为左边部分 right_half = arr[mid:] # 划分为右边部分 merge_sort(left_half) # 递归排序左边部分 merge_sort(right_half) # 递归排序右边部分 i = j = k = 0 # 初始化索引变量 # 合并两个已排序的子列表 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 # 检查是否有剩余项 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 # 测试代码 if __name__ == "__main__": example_array = [4, 5, 3, 3, 1, 2, 2, 4] print("给定数组:", example_array) merge_sort(example_array) print("排序后的数组:", example_array) ``` 这段代码清晰地描述了如何通过递归分解以及后续的合并过程完成排序任务[^2]。 --- #### C语言实现归并排序 对于熟悉底层编程的语言如C来说，归并排序同样适用。这里提供一个简单的C语言版本： ```c #include <stdio.h> void merge(int array[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; // 定义左侧和右侧临时数组 for (i = 0; i < n1; i++) // 填充左侧数组 L[i] = array[l + i]; for (j = 0; j < n2; j++) // 填充右侧数组 R[j] = array[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { // 合并两个数组 if (L[i] <= R[j]) array[k++] = L[i++]; else array[k++] = R[j++]; } while (i < n1) // 添加剩余的左侧元素 array[k++] = L[i++]; while (j < n2) // 添加剩余的右侧元素 array[k++] = R[j++]; } void mergeSort(int array[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; // 计算中间位置 mergeSort(array, l, m); // 排序左侧部分 mergeSort(array, m + 1, r);// 排序右侧部分 merge(array, l, m, r); // 合并两侧 } } // 主函数测试 int main() { int array[] = {4, 5, 3, 3, 1, 2, 2, 4}; int size = sizeof(array)/sizeof(array[0]); printf("给定数组: "); for (int i=0;i<size;i++) printf("%d ",array[i]); printf("\n"); mergeSort(array, 0, size-1); printf("排序后的数组: "); for (int i=0;i<size;i++) printf("%d ",array[i]); printf("\n"); return 0; } ``` 该程序演示了如何在C语言环境中应用归并排序技术[^3]。 ---