首页 > 代码库 > 【数据结构与算法】二路归并排序
【数据结构与算法】二路归并排序
二路归并排序的时间复杂度是O(n*log2n),空间复杂度是O(n)。
代码如下:
/** * 源码名称:MergeSort.java * 日期:2014-08-11 * 程序功能:合并排序 * 版权:CopyRight@A2BGeek * 作者:A2BGeek */ public class MergeSort { public void mergeSort(int[] in) { int length = in.length; int tmp[] = new int[length]; mergePass(in, tmp, 0, length - 1); } public void mergePass(int[] in, int[] tmp, int start, int end) { if (start == end) { return; } else { int mid = (start + end) / 2; mergePass(in, tmp, start, mid); mergePass(in, tmp, mid + 1, end); merge2Sub(in, tmp, start, mid, end); } } /** * 函 数 名:merge2Sub * 功能描述:合并相邻的有序表 * 输入参数: * @param a 待排序数组 * @param tmp 临时用于交换数据 * @param start 第一个有序表的起点索引 * @param mid 第一个有序表的终点索引 * @param end 第二个有序表的终点索引 */ public void merge2Sub(int[] a, int[] tmp, int start, int mid, int end) { int i = start; int j = mid + 1; int k = 0; while (i <= mid && j <= end) { if (a[i] <= a[j]) { tmp[k] = a[i]; i++; k++; } else { tmp[k] = a[j]; j++; k++; } } while (i <= mid) { tmp[k] = a[i]; i++; k++; } while (j <= end) { tmp[k] = a[j]; j++; k++; } for (int index = 0; index < end - start + 1; index++) { a[start + index] = tmp[index]; } printArray(a); } public void printArray(int[] in) { for (int i : in) { System.out.print(i + " "); } System.out.println(); } public static void main(String[] args) { int[] testCase = { 1, 3, 4, 10, 2, 5, 6, 7, 9, 11 }; MergeSort mMergeSort = new MergeSort(); mMergeSort.printArray(testCase); mMergeSort.mergeSort(testCase); mMergeSort.printArray(testCase); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。