首页  

归并排序     所属分类 algo 浏览量 627
把数组分成两半,递归地排好每一半,合并有序的两半
稳定排序 
需要辅助空间 非就地排序
归并排序之父 冯诺依曼


public class MergeSort { public static void main(String[] args) throws Exception { int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 }; mergeSort(arr); printArr(arr); } public static void mergeSort(int[] a) { if (a == null || a.length <= 1) { return; } // a.length - 1 !!! mergeSort(a, 0, a.length - 1); } public static void mergeSort(int[] a, int low, int high) { int mid = (low + high) / 2; if (low < high) { mergeSort(a, low, mid); mergeSort(a, mid + 1, high); merge(a, low, mid, high); } } private static void merge(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low; int j = mid + 1; int k = 0; while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 左边剩下的数放入数组 while (i <= mid) { temp[k++] = a[i++]; } // 右边剩下的数放入数组 while (j <= high) { temp[k++] = a[j++]; } // for (int x = 0; x < temp.length; x++) { a[x + low] = temp[x]; } } private static void printArr(int[] arr) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < arr.length; i++) { sb.append(arr[i]).append(" "); } System.out.println(sb.toString()); } }
https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/MergeSort.java
归并排序与快速排序

上一篇     下一篇
Fibonacci数列第N位计算

《七堂极简物理课》摘录

微积分的一些知识点

行为金融学简介

MSCI中国A50指数

美术英语词汇