// 归并排序的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("排序后的数组: ");
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) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
}
main
函数:这是程序的入口点。它定义了一个待排序的数组,并调用 mergeSort
函数对其进行排序,最后打印排序前后的数组。
mergeSort
函数:这是归并排序的核心递归函数。它将数组分成两半,分别对每一半进行递归排序,然后调用 merge
函数将两个已排序的子数组合并。
merge
函数:该函数负责将两个已排序的子数组合并成一个有序的数组。它首先将子数组复制到临时数组中,然后通过比较临时数组中的元素,逐步将较小的元素放回原数组中。
printArray
函数:这是一个辅助函数,用于打印数组的内容。
归并排序的时间复杂度为 O(n log n),是一种稳定的排序算法。
上一篇:java 时间格式转换
下一篇:java prometheus
Laravel PHP 深圳智简公司。版权所有©2023-2043 LaravelPHP 粤ICP备2021048745号-3
Laravel 中文站