归并排序 - 非递归实现

import java.util.Arrays;/*** @title MergeSortByNonRecursion* @description 归并排序，非递归实现* author zzw* version 1.0.0* create 2024/10/23 22:17**/
public class MergeSortByNonRecursion {public static void main(String[] args) {int[] nums = {5, 1, 1, 2, 0, 0};new MergeSortByNonRecursion().sortArray(nums);System.out.println(Arrays.toString(nums));}public int[] sortArray(int[] nums) {sort(nums);return nums;}/*** 归并排序，非递归处理<br/>* <ol>*     <li>每次将相邻的两个有序数组进行合并</li>*     <li>先从只有一个节点的数组开始（一个节点默认有序，无需做其他处理），从做向右合并</li>*     <li>将数组处理完一遍后，将节点个数增大一倍，将合并好的子数组再进行合并</li>* </ol>** @param arr 排序数组*/public static void sort(int[] arr) {// 每次用来合并的子数组中的元素个数，每次增加一倍for (int i = 1; i < arr.length; i <<= 1) {// 默认左侧数据的起始节点从0开始int leftIndex = 0;// 计算出中间节点int mid = leftIndex + i - 1;// 只有中间节点小于数组长度减一的时候，才能保证左右两侧数组都存在数据，这样才需要进行数组的合并while (mid < arr.length - 1) {// 计算出右侧子数组的最后一个节点下标// 该下标取中间节点加子数组长度个数 和 总数组长度的最小值，避免数组越界int right = Math.min((mid + i), arr.length - 1);// 进行数组合并merge(arr, leftIndex, mid, right);// 计算下一组需要合并的子数组的左侧数组起始位置leftIndex = right + 1;// 计算下一组需要合并的子数组的左侧数组终止位置// 这里计算用于判断是否还有数据数据放入右侧数组进行合并mid = leftIndex + i - 1;}}}/*** 合并两个有序数组** @param arr   两个有序数组所在的有序数据* @param left  左侧有序数据在arr数组中的起始位置* @param mid   左侧有序数组在arr数组中的终点位置* @param right 右侧有序数组在arr数组中的终点位置，起始位置在mid+1处*/public static void merge(int[] arr, int left, int mid, int right) {// 使用一个临时数据存放合并后的数据int[] tmp = new int[right - left + 1];// 临时数据数据合并到的下标int i = 0;// 左侧有序数据处理到的位置int lIndex = left;// 右侧有序数据处理到的位置int rIndex = mid + 1;// 比较左、右两侧的有序数组，谁的值小，将谁放到临时数组中，// 然后将临时数组、取值的哪个数组的处理下标向后移动// 直到左、右两侧的数组有一个处理完，停止此次处理while (lIndex <= mid && rIndex <= right) {tmp[i++] = arr[lIndex] <= arr[rIndex] ? arr[lIndex++] : arr[rIndex++];}// 如果左侧的有序数组没有处理完，将左侧数组的剩余数据放入临时数组中while (lIndex <= mid) {tmp[i++] = arr[lIndex++];}// 如果右侧的有序数组没有处理完，将右侧数组的剩余数据放入临时数组中while (rIndex <= right) {tmp[i++] = arr[rIndex++];}// 将临时数组中的数据放回原来的数据中for (int j = 0; j < i; j++) {arr[j + left] = tmp[j];}}}