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]; } } }