归并排序(JAVA)
package org.rev.algorithm; /** * 归并排序,属于交换排序,时间复杂度为算法复杂度Ο(n log n),比快排序慢,但稳定。 * * 1. 将一个序列递归拆分成多个有序的子序列。 * * 2. 递归合并这些子序列,成为完整的子序列。 * */ public class MergeSort { public static void main(String[] args) { int[] data = {39, 11, 38, 97, 86, 37, 12, 4, 51, 18}; // 归并排序 MergeSort ms = new MergeSort(); ms.sort(data); System.out.println("排序之后:"); ms.printData(data); } public void sort(int[] data) { if (data.length > 0) { // length是0,就不能减1了。 mergeSort(data, 0, data.length - 1); } } public void mergeSort(int[] data, int left, int right) { if (left < right) { int middle = (left + right) / 2; System.out.println("left is:" + left + ", right is:" + right + ", middle is:" + middle + ", data[" + middle + "]=" + data[middle]); mergeSort(data, left, middle); // 对左边进行递归 mergeSort(data, middle + 1, right); // 对右边进行递归 merge(data, left, middle, right); // 归并 printData(data); } } /** * 归并两个数组,归并前两个数组是有序的,归并后的数组也是有序的。 * * @param data 数组对象 * @param left 左数组第一个元素的索引 * @param middle 左数组的最后一个元素的索引,middle+1是右数组第一个元素的索引 * @param right 右数组最后一个元素的索引 */ private void merge(int[] data, int left, int middle, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右边的第一个元素的索引 int mid = middle + 1; // tmp 临时变量,缓存左数组第一个元素的索引 int tmp = left; // third 记录临时数组的索引 int third = left; while (left <= middle && mid <= right) { // 从两个数组中选取较小的数放入临时数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 将剩余的部分放入临时数组 while (left <= middle) { tmpArr[third++] = data[left++]; } while (mid <= right) { tmpArr[third++] = data[mid++]; } // 将临时数组复制回原数组 while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } /* * 打印输出数组中的数据 */ private void printData(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。