Java程序实现归并排序算法
要理解这个示例,你应该具备以下 Java 编程 主题的知识:
Java 中的归并排序
归并排序算法基于分而治之的原则,即将一个问题分解成多个子问题。每个子问题分别解决后,再将子问题的解决方案组合成最终的解决方案。
要了解更多,请访问 归并排序算法。
示例:Java 程序实现归并排序算法
import java.util.Arrays;
// Java 中的归并排序
class Main {
// 将两个子数组 L 和 M 合并为一个数组
void merge(int array[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1];
int M[] = new int[n2];
// 填充左右数组
for (int i = 0; i < n1; i++)
L[i] = array[p + i];
for (int j = 0; j < n2; j++)
M[j] = array[q + 1 + j];
// 维护子数组和主数组的当前索引
int i, j, k;
i = 0;
j = 0;
k = p;
// 直到 L 或 M 的任一端结束,从 L 和 M 中选取较大的元素,并放在 A[p..r] 的正确位置
// 用于降序排序
// 使用 if(L[i] >= M[j])
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
array[k] = L[i];
i++;
} else {
array[k] = M[j];
j++;
}
k++;
}
// 当 L 或 M 的元素用完时,
// 取剩余元素放入 A[p..r]
while (i < n1) {
array[k] = L[i];
i++;
k++;
}
while (j < n2) {
array[k] = M[j];
j++;
k++;
}
}
// 将数组分成两个子数组,排序并合并它们
void mergeSort(int array[], int left, int right) {
if (left < right) {
// m 是将数组分成两个子数组的点
int mid = (left + right) / 2;
// 递归调用每个子数组
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// 合并已排序的子数组
merge(array, left, mid, right);
}
}
public static void main(String args[]) {
// 创建一个未排序的数组
int[] array = { 6, 5, 12, 10, 9, 1 };
Main ob = new Main();
// 调用方法 mergeSort()
// 传递参数:数组,起始索引和末尾索引
ob.mergeSort(array, 0, array.length - 1);
System.out.println("排序后的数组:");
System.out.println(Arrays.toString(array));
}
}
输出 1
未排序的数组:
[6, 5, 12, 10, 9, 1]
排序后的数组:
[1, 5, 6, 9, 10, 12]
这里,数组的元素按升序排列。如果我们想按降序排序元素,那么在 merge()
方法的第一个 while
循环中,我们可以更改代码为:
// 小于号更改为大于号
if (L[i] >= M[j]) {