茂名做网站建设公司,可信赖的镇江网站建设,微信公众平台二次开发,免费ppt模板下载医学归并排序#xff08;Merge Sort#xff09;是一种基于分治法的排序算法。它将一个大数组分成两个较小的子数组#xff0c;分别对每个子数组进行排序#xff0c;然后再将这两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度为 O(n log n)#xff0c;其中…归并排序Merge Sort是一种基于分治法的排序算法。它将一个大数组分成两个较小的子数组分别对每个子数组进行排序然后再将这两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度为 O(n log n)其中 n 是数组的大小。
以下是一个 Java 实现归并排序的示例
public class MergeSort { // 主函数用于测试归并排序 public static void main(String[] args) { int[] array {38, 27, 43, 3, 9, 82, 10}; System.out.println(给定数组:); printArray(array); mergeSort(array, 0, array.length - 1); System.out.println(\n排序后的数组:); printArray(array); } // 归并排序函数 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); } } // 合并函数 public static void merge(int[] array, int left, int middle, int right) { // 找到两个子数组的大小 int n1 middle - left 1; int n2 right - middle; // 创建临时数组 int[] leftArray new int[n1]; int[] rightArray new int[n2]; // 拷贝数据到临时数组 for (int i 0; i n1; i) leftArray[i] array[left i]; for (int j 0; j n2; j) rightArray[j] array[middle 1 j]; // 合并临时数组到原数组 // 初始索引分别为两个子数组的起始位置 int i 0, j 0; // 初始索引为合并子数组的起始位置 int k left; while (i n1 j n2) { if (leftArray[i] rightArray[j]) { array[k] leftArray[i]; i; } else { array[k] rightArray[j]; j; } k; } // 拷贝左子数组剩余的元素如果有 while (i n1) { array[k] leftArray[i]; i; k; } // 拷贝右子数组剩余的元素如果有 while (j n2) { array[k] rightArray[j]; j; k; } } // 打印数组函数 public static void printArray(int[] array) { int n array.length; for (int i 0; i n; i) System.out.print(array[i] ); System.out.println(); }
}
代码解释
mergeSort 方法 递归地将数组分成左右两部分直到每部分只有一个元素或为空。递归调用 mergeSort 方法对左右两部分进行排序。调用 merge 方法将已排序的左右两部分合并成一个完整的已排序数组。merge 方法 创建两个临时数组 leftArray 和 rightArray 分别存储左右两部分。将左右两部分分别拷贝到临时数组中。使用两个指针 i 和 j 分别遍历临时数组 leftArray 和 rightArray。使用一个指针 k 遍历原数组根据临时数组中的元素大小将较小的元素依次拷贝回原数组。如果某一临时数组的元素已经拷贝完则将另一临时数组的剩余元素拷贝回原数组。printArray 方法 用于打印数组中的元素。
运行结果
程序运行后会先打印给定的数组然后打印排序后的数组。
归并排序是一个稳定的排序算法适用于大多数需要排序的场景。它的空间复杂度为 O(n)因为需要额外的临时数组来存储子数组的元素。
