归并排序是一种高级排序算法,本文介绍了归并排序的 Java 实现。
归并排序
归并算法,Merge Sort,是建立在归并操作上的一种有效的排序算,时间复杂度为 O(nlogn)
。
1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
归并算法执行流程:
分割:递归地把当前序列平均分割成两半。
集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。
示意图
使用合并排序为一列数字进行排序的过程
使用合并排序为一列数字进行排序的过程
复杂度
复杂度 |
值 |
平均时间复杂度 |
O(nlogn) |
最坏时间复杂度 |
O(nlogn) |
最优时间复杂度 |
O(nlogn) |
空间复杂度 |
O(n) |
稳定性 |
稳定 |
Java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| public class MergeSort {
public static void sort(Comparable[] arr) { sort(arr, 0, arr.length - 1); }
private static void sort(Comparable[] arr, int left, int right) { if (left >= right) { return; } int mid = (left + right) >>> 1; sort(arr, left, mid); sort(arr, mid + 1, right); merge(arr, left, mid, right); }
private static void merge(Comparable[] arr, int left, int mid, int right) { Comparable[] temp = Arrays.copyOfRange(arr, left, right + 1); int i = left; int j = mid + 1; for (int k = left; k <= right; k++) { if (i > mid) { arr[k] = temp[j - left]; j++; } else if (j > right) { arr[k] = temp[i - left]; i++; } else if (temp[i - left].compareTo(temp[j - left]) > 0) { arr[k] = temp[j - left]; j++; } else { arr[k] = temp[i - left]; i++; } } } }
|
总结
归并排序是由冯·诺依曼提出的一种高级排序算法,主要流程有:分割、集成两个过程。归并排序的平均、最坏、最好时间复杂度都是O(nlogn),是一种稳定的排序算法。Java 主要排序方法为 java.util.Arrays.sort(),对于引用数据类型使用归并排序。
参考