Java排序号更新逻辑

前言

在工作上遇到一个比较奇怪的逻辑, 根据唯一字段排序并且序号不得重复。这样的逻辑很可能会涉及到批量更新, 锁表等, 并不值得推荐。当然有历史原因不得不这样做。好的程序不只建立在程序本身上, 更加建立在优秀的逻辑设计上。本文仅作参考。

实现

1. 首先定义一个需要排序的实体

package com.example.javademo.sort;

import lombok.Data;

/**
 * @author cuishiying
 * @date 2021-07-23
 */
@Data
public class Node {
    private Integer id;
    private String name;
    private Integer sortIndex;

    public Node(Integer id, String name, Integer sortIndex) {
        this.id = id;
        this.name = name;
        this.sortIndex = sortIndex;
    }
}

2. 然后就是我们的算法逻辑

package com.example.javademo.sort;

import org.springframework.util.Assert;
import java.util.Comparator;
import java.util.List;

/**
 * 本排序方法适用于数据量较小的排序, 业务中要求按找1个字段排序且排序值需要唯一
 * 优秀的排序方案来源于优秀的产品设计及优秀的业务设计, 如根据排序值+更新时间多字段来决定排序等
 *
 * 排序类型分为几种
 * 1. 序号值刚好在目标位置, 无需排序
 * 2. 目标位置存在间隙, 可以直接插入
 * 3. 目标位置间隙为1, 需要重排
 *
 * @author cuishiying
 * @date 2021-07-23
 */
public class SortHandler {

    /**
     * 步长
     */
    private static final Integer STEP = 10;

    /**
     * 更新排序值
     * @param sortedNodes 参与排序的所有对象(默认正序)
     * @param targetNodeId 需要调整排序的对象id
     * @param targetPosition 目标位置(从1开始, index=position-1)
     */
    public void updateSortIndex(List<Node> sortedNodes, Integer targetNodeId, Integer targetPosition) {
        Assert.isTrue(targetPosition > 0, "序号必须>0");

        Node targetNode = sortedNodes.stream().filter(node -> node.getId().equals(targetNodeId)).findFirst().orElse(null);
        Assert.notNull(targetNode, String.format("id=%s的对象不存在", targetNodeId));

        // 1. 判断是否存在相同序号的node, 如果存在则重排
        long distinctCount = sortedNodes.stream().map(Node::getSortIndex).distinct().count();
        if (distinctCount < sortedNodes.size()) {
            System.out.println("存在重复序号");
            resortIndex(sortedNodes);
        }

        // 2. 判断当前位置是否是目标位置
        int currentIndex = sortedNodes.indexOf(targetNode);
        if (currentIndex == targetPosition - 1) {
            System.out.println("当前位置即是目标位置, 无需排序");
            return;
        }

        /**
         * 3. 判断目标位置是否存在间隙, 可以直接插入。
         * a. 如果移动元素当前在left位置, 目标位置在right位置, 则移动后左侧元素会变少, 应该+1的位置寻找目标位置
         * eg: N1,N2,N3,N4, 将N2的序号改为3, 则应该在N3和N4之间插入N2, 然后移除原始N2
         * b. 如果移动元素当前在right位置, 目标位置在left位置, 则可以直接插入
         */
        if (currentIndex < targetPosition - 1) {
            int leftIndex = targetPosition - 1;
            int rightIndex = targetPosition;
            if (rightIndex > sortedNodes.size() - 1) {
                int maxSortIndex = getMaxSortIndex(sortedNodes);
                targetNode.setSortIndex(maxSortIndex + STEP);
                System.out.println("目标右移, 尾部直接插入:");
                log(sortedNodes);
                return;
            }
            Integer rightSortIndex = sortedNodes.get(rightIndex).getSortIndex();
            Integer leftSortIndex = sortedNodes.get(leftIndex).getSortIndex();
            if (rightSortIndex - leftSortIndex > 1) {
                // 计算所得目标排序号
                int targetSortIndex = leftSortIndex + (rightSortIndex - leftSortIndex) / 2;
                targetNode.setSortIndex(targetSortIndex);
                System.out.println("目标右移, 间隙>1, 可以直接插入:");
                log(sortedNodes);
            } else {
                System.out.println("目标右移, 间隙<1, 需要重排序");
                sortedNodes.add(targetPosition - 1, sortedNodes.remove(sortedNodes.indexOf(targetNode)));
                resortIndex(sortedNodes);
            }
            return;
        }

        if (currentIndex > targetPosition - 1) {
            int leftIndex = targetPosition - 2;
            int rightIndex = targetPosition - 1;
            if (leftIndex < 0) {
                int minSortIndex = getMinSortIndex(sortedNodes);
                if (minSortIndex > 1) {
                    // 计算所得目标排序号
                    int targetSortIndex = 1 + (minSortIndex - 1) / 2;
                    targetNode.setSortIndex(targetSortIndex);
                    System.out.println("目标左移, 间隙>1, 头部直接插入:");
                    log(sortedNodes);
                } else {
                    System.out.println("目标左移, 间隙<1, 需要重排序");
                    sortedNodes.add(targetPosition - 1, sortedNodes.remove(sortedNodes.indexOf(targetNode)));
                    resortIndex(sortedNodes);
                }
                return;
            }
            Integer rightSortIndex = sortedNodes.get(rightIndex).getSortIndex();
            Integer leftSortIndex = sortedNodes.get(leftIndex).getSortIndex();
            if (rightSortIndex - leftSortIndex > 1) {
                // 计算所得目标排序号
                int targetSortIndex = leftSortIndex + (rightSortIndex - leftSortIndex) / 2;
                targetNode.setSortIndex(targetSortIndex);
                System.out.println("目标左移, 间隙>1, 可以直接插入:");
                log(sortedNodes);
            } else {
                System.out.println("目标左移, 间隙<1, 需要重排序");
                sortedNodes.add(targetPosition - 1, sortedNodes.remove(sortedNodes.indexOf(targetNode)));
                resortIndex(sortedNodes);
            }
            return;
        }

    }

    /**
     * 获取当前分组最大序号
     * @param sortedNodes 原始list
     * @return 最大序号
     */
    private int getMaxSortIndex(List<Node> sortedNodes) {
        return sortedNodes.stream().mapToInt(Node::getSortIndex).max().orElse(1);
    }

    /**
     * 获取当前分组最小序号
     * @param sortedNodes 原始list
     * @return 最小序号
     */
    private int getMinSortIndex(List<Node> sortedNodes) {
        return sortedNodes.stream().mapToInt(Node::getSortIndex).min().orElse(1);
    }


    /**
     * 数据整体重排序
     *
     * 需要重排序的时候集合现在内存中做好排序, 然后重新编排序号, 并更新数据库
     * sortedNodes.add(targetIndex - 1, sortedNodes.remove(sortedNodes.indexOf(targetNode)));
     * @param sortedNodes 原始顺序list
     */
    private void resortIndex(List<Node> sortedNodes) {
        for (int i = 0; i < sortedNodes.size(); i++) {
            Node node = sortedNodes.get(i);
            node.setSortIndex(STEP * i + 1);
        }
        System.out.println("重排序:");
        log(sortedNodes);
    }

    private void log(List<Node> sortedNodes) {
        sortedNodes.stream().sorted(Comparator.comparing(Node::getSortIndex)).forEach(System.out::println);
    }
}

3. 最后验证下结果是否复合预期

package com.example.javademo.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cuishiying
 * @date 2021-07-23
 */
@Slf4j
public class SortTest {

    public static void main(String[] args) {
        // 初始化数据
        List<Node> nodes = initData();
        System.out.println("原始数据:");
        nodes.forEach(System.out::println);
        // 更新排序值
        SortHandler sortHandler = new SortHandler();
        Node targetNode = nodes.get(2);
        int targetPosition = 3;
        System.out.printf("排序计划:node%s -> position%s\n", targetNode.getId(), targetPosition);
        sortHandler.updateSortIndex(nodes, targetNode.getId(), targetPosition);
    }

    private static List<Node> initData() {
        List<Node> data = new ArrayList<>(10);
        for (int i = 0; i < 5; i++) {
            Node node = new Node(i + 1, "node" + (i + 1), i * 2 + 1);
            data.add(node);
        }
        return data;
    }
}

最后

本文到此结束，感谢阅读。如果您觉得不错，请关注公众号【当我遇上你】支持一下。