在此示例中,我们将学习在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] >= <[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]) {