问题说明
什么是针对元素小组的归并排序算法，举个例子：假如有一个数组[1,2,3,4,5,6,7,8,9]，{1,2,3}为一个小组，{4,5,6}为一个小组，{7,8,9}为一个小组，现需要根据每个小组的第一个元素来进行排序，小组需要一起移动，则降序排序之后的数组为[7,8,9,4,5,6,1,2,3]。
为什么需要这样排序呢，这样有什么好处？比如需要存储多条线段，每根线段有三个属性，分别为x、minY、maxY，如图所示
是不是很容易想到使用List<int[]>来存储，每个int[]存储一条线段，虽然这样很容易实现，但是这样不仅会占用更多的内存，后面在使用的时候速度也会比较慢。为了节省内存和后面使用的内存，可以只用一个List<Integer>来存储线段，只需要三个相连的元素来一起表示一条线段即可，比如索引[0,1,2]的三个元素一起表示一条线段，索引[3,4,5]的三个元素一起表示另一条线段。
使用这种方式，在遍历线段的时候非常简单，直接使用for(int i=0; i<list.size(); i+=3)，每次分别取出i、i+1、i+2对应的元素即可。但是如果想要对线段排序呢？很多读者是不是没有写过类似的程序，本文提供一种排序方法供读者参考
基于元素小组归并排序算法
首先为什么要基于归并排序算法来实现呢？因为归并排序的平均情况、最好情况、最坏情况的时间复杂度都是O(n log n)，性能较好
归并排序原理
归并排序使用分治思想，“分"即将大数组变成小数组，“治”即将小数组合并为大数组，并在合并的过程中进行排序
集合版本
【抽象排序类】
其中compare为抽象方法，需要子类去自定义排序规则
package com.dam.algorithm.version3.merge; import java.util.List; /** * @Author dam * @create 2023/9/13 14:39 */ public abstract class GroupMergeSort { /** * @param list * @param groupSize 组的大小 */ public void sort(List<Integer> list, int groupSize) { // 归并排序需要一个额外空间来存储排序之后的数组 int[] temp = new int[list.size()]; mergeSort(list, 0, list.size() / groupSize - 1, temp, groupSize); } /** * 分+合方法 * * @param arr * @param left * @param right * @param temp */ private void mergeSort(List<Integer> arr, int left, int right, int[] temp, int groupSize) { // 只要left<right，就可以继续分 if (left < right) { // 中间索引 int mid = (left + right) / 2; // 向左递归进行分解 mergeSort(arr, left, mid, temp, groupSize); // 向右递归进行分解 mergeSort(arr, mid + 1, right, temp, groupSize); // 合并（最先合并栈顶的元素） merge(arr, left, mid, right, temp, groupSize); } } /** * 合并的方法 * * @param list 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ private void merge(List<Integer> list, int left, int mid, int right, int[] temp, int groupSize) { // 初始化i, 左边有序序列的初始索引 int i = left; // 初始化j, 右边有序序列的初始索引 int j = mid + 1; // 指向temp数组的当前索引 int cur = 0; /// 先把左右两边(有序)的数据按照规则填充到temp数组，直到左右两边的有序序列，有一边处理完毕为止 while (i <= mid && j <= right) { if (compare(list.get(groupSize * i), list.get(groupSize * j))) { // --if-- 如果compare方法返回true，这里的compare由用户自定义，即将左边的当前元素填充到temp数组中 setValueFromListToArr(temp, cur, list, i, groupSize); cur += 1; i += 1; } else { // 否则，将右边有序序列的当前元素填充到temp数组 setValueFromListToArr(temp, cur, list, j, groupSize); cur += 1; j += 1; } } /// 把有剩余数据的一边的数据依次全部填充到temp while (i <= mid) { // --if-- 左边的有序序列还有剩余的元素，就全部填充到temp setValueFromListToArr(temp, cur, list, i, groupSize); cur += 1; i += 1; } while (j <= right) { // --if-- 右边的有序序列还有剩余的元素，就全部填充到temp setValueFromListToArr(temp, cur, list, j, groupSize); cur += 1; j += 1; } /// 将temp数组的元素拷贝到list中 cur = 0; int tempLeft = left; while (tempLeft <= right) { setValueFromArrToList(list, tempLeft, temp, cur, groupSize); cur += 1; tempLeft += 1; } } /** * 如果想要 升序 ，那num1<num2的时候就返回true ; 反之为降序 * * @param num1 * @param num2 * @return */ public abstract boolean compare(Integer num1, Integer num2); /** * 定义方法以交换两个组中的元素，将集合的小组的元素设置到数组的小组中 * 例如：切换第1组和第2组。我们需要将第1组的所有元素与第2组的所有元素交换 * @param receiptArr * @param receiveIndex * @param sendList * @param sendIndex * @param groupSize */ private void setValueFromListToArr(int[] receiptArr, int receiveIndex, List<Integer> sendList, int sendIndex, int groupSize) { for (int i = 0; i < groupSize; i++) { receiptArr[groupSize * receiveIndex + i] = sendList.get(groupSize * sendIndex + i); } } private void setValueFromArrToList(List<Integer> receiptList, int receiveIndex, int[] sendArr, int sendIndex, int groupSize) { // 一次设置多个元素 for (int i = 0; i < groupSize; i++) { receiptList.set(groupSize * receiveIndex + i, sendArr[groupSize * sendIndex + i]); } } }
【子类】
package com.dam.algorithm.version3.merge; import com.dam.algorithm.version3.shell.GroupShellSort; /** * @Author dam * @create 2023/9/13 13:55 */ public class VScanLineGroupMergeSort extends GroupMergeSort { /** * 单例模式 */ private static volatile VScanLineGroupMergeSort instance; private VScanLineGroupMergeSort() { } public static VScanLineGroupMergeSort getInstance() { if (instance == null) { synchronized (VScanLineGroupMergeSort.class) { if (instance == null) { instance = new VScanLineGroupMergeSort(); } } } return instance; } @Override public boolean compare(Integer num1, Integer num2) { // 如果num1更小，先填充num1到temp中，说明排序类型为升序排序 if (num1 < num2) { return true; } return false; } }
数组版本
package com.dam.algorithm.version3.merge; /** * @Author dam * @create 2023/9/13 14:39 */ public class GroupMergeSortTest { public static void main(String[] args) { int[] array = {3, 5, 1, 2, 7, 6, 8, 9, 4, 1, 9, 17}; int groupSize = 3; // 排序 sort(array, groupSize); // 打印排序后的数组 for (int i : array) { System.out.print(i + " "); } } public static void sort(int[] arr, int groupSize) { int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length / groupSize - 1, temp, groupSize); } public static void mergeSort(int[] arr, int left, int right, int[] temp, int groupSize) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid, temp, groupSize); mergeSort(arr, mid + 1, right, temp, groupSize); merge(arr, left, mid, right, temp, groupSize); } } public static void merge(int[] arr, int left, int mid, int right, int[] temp, int groupSize) { int i = left; int j = mid + 1; int cur = 0; while (i <= mid && j <= right) { if (compare(arr[groupSize * i], arr[groupSize * j])) { setValueFromSendToReceive(temp, cur, arr, i, groupSize); cur += 1; i += 1; } else { setValueFromSendToReceive(temp, cur, arr, j, groupSize); cur += 1; j += 1; } } while (i <= mid) { setValueFromSendToReceive(temp, cur, arr, i, groupSize); cur += 1; i += 1; } while (j <= right) { setValueFromSendToReceive(temp, cur, arr, j, groupSize); cur += 1; j += 1; } cur = 0; int tempLeft = left; while (tempLeft <= right) { setValueFromSendToReceive(arr, tempLeft, temp, cur, groupSize); cur += 1; tempLeft += 1; } } public static void setValueFromSendToReceive(int[] receiptArr, int receiveIndex, int[] sendArr, int sendIndex, int groupSize) { for (int i = 0; i < groupSize; i++) { receiptArr[groupSize * receiveIndex + i] = sendArr[groupSize * sendIndex + i]; } } public static boolean compare(Integer num1, Integer num2) { if (num1 < num2) { return true; } return false; } }
