算法系列3—排序算法之归并排序(MergeSort)

算法步骤

1. 把长度为n的输入序列分成两个长度为n/2的子序列;
2. 对这两个子序列分别采用归并排序;
3. 将两个排序好的子序列合并成一个最终的排序序列。

动图展示

代码实现

  public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);}private static void mergeSort(int[] arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}// 将arr[left...mid]和arr[mid+1...right]两部分进行归并private static void merge(int[] arr, int left, int mid, int right) {int[] aux = Arrays.copyOfRange(arr, left, right + 1);// 初始化，leftIndex指向左半部分的起始索引位置left；rightIndex指向右半部分起始索引位置mid+1int leftIndex = left, rightIndex = mid + 1;for (int k = leftIndex; k <= right; k++) {if (leftIndex > mid) {                                                  // 如果左半部分元素已经全部处理完毕arr[k] = aux[rightIndex - left];rightIndex++;} else if (rightIndex > right) {                                        // 如果右半部分元素已经全部处理完毕arr[k] = aux[leftIndex - left];leftIndex++;} else if (aux[leftIndex - left] < aux[rightIndex - left]) {            // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[leftIndex - left];leftIndex++;} else {                                                                // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[rightIndex - left];rightIndex++;}}}