实时插入排序算法

目录
  • 背景
  • 理论
  • 代码实现

    • 1. 比较器
    • 2. 节点

      • 2.1 节点抽象类
      • 2.2 虚拟头节点
      • 2.3 虚拟尾节点
      • 2.4 普通节点
    • 3. 链表

      • 3.1 链表结构抽象类
      • 3.2 链表结构类
    • 4. 测试

      • 4.1 用户类
      • 4.2 测试类
  • 总结

背景

在正常的工作中,我们经常遇到从消息队列中接收一天的数据量,并对其进行排序的场景。那么,我们通常会想到最经典的十大经典排序算法。确实,这些算法都可以满足我们的场景需要,,但如果我们要求接收消息过程中,实时进行排序呢?这些算法显然都不能满足需求,它们都是在接收到所有数据后,再统一排序。所以,今天,我们动手自己遍写一个实时插入排序算法!

理论

参考插入排序算法,我们将接收到的数据存放在一个链表结构当中,每接收一个新数据,就让它与已存在的数据逐个比较,找到需要插入的位置下一个节点,执行新节点插入操作!

实时插入排序算法插图

代码实现

1. 比较器

因为要进行排序,所以我们需要先建立一个比较器接口,来保证用户自定义比较方法。

package cn.wxson.sort.comparator;

import cn.wxson.sort.node.AbstractNode;
import com.sun.istack.internal.NotNull;

/**
 * Title 比较器
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
@FunctionalInterface
public interface AbstractComparator<T> {

    /**
     * 比较方法
     *
     * @param one 数据节点一
     * @param two 数据节点二
     * @return 比较结果
     */
    boolean compare(@NotNull AbstractNode<T> one, @NotNull AbstractNode<T> two);
}

2. 节点

2.1 节点抽象类

创建节点抽象类,存放数据,并利用比较器实现比较逻辑。

package cn.wxson.sort.node;

import cn.wxson.sort.comparator.AbstractComparator;
import lombok.Getter;
import lombok.Setter;

/**
 * Title 节点
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
@Setter
@Getter
public abstract class AbstractNode<T> {

    /**
     * 前一个节点
     */
    private AbstractNode<T> pre;
    /**
     * 后一个节点
     */
    private AbstractNode<T> next;
    /**
     * 节点内存储的实际数据
     */
    protected T t;

    /**
     * 无参构造
     */
    public AbstractNode() {
        super();
    }

    /**
     * 带参构造
     *
     * @param t 数据对象
     */
    public AbstractNode(T t) {
        this.t = t;
    }

    /**
     * 获取数据比较器
     *
     * @return 比较器对象
     */
    protected abstract AbstractComparator<T> comparator();

    /**
     * 数据比较
     *
     * @param data 数据节点
     */
    public AbstractNode<T> compareTo(AbstractNode<T> data) {
        return this.comparator().compare(this, data) ? this : this.next.compareTo(data);
    }
}

2.2 虚拟头节点

头节点是一个虚拟节点,只做传递给下个节点操作,自身实现比较器,数据比较时永远排在第一位。

package cn.wxson.sort.node;

import cn.wxson.sort.comparator.AbstractComparator;

/**
 * Title   虚拟头节点
 * 只做传递给下个节点操作,数据比较永远排在第一位
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
public final class DummyHeadNode<T> extends AbstractNode<T> implements AbstractComparator<T> {

    /**
     * 获取数据比较器
     *
     * @return 比较器对象
     */
    @Override
    protected AbstractComparator<T> comparator() {
        return this;
    }

    /**
     * 比较方法
     * 头节点永远排在第一位
     *
     * @param one 节点一
     * @param two 节点二
     * @return 比较结果
     */
    @Override
    public boolean compare(AbstractNode<T> one, AbstractNode<T> two) {
        return false;
    }
}

2.3 虚拟尾节点

尾节点也是一个虚拟节点,不需要做任务传递操作,自身实现比较器,排序时永远排在链表最后一位。

package cn.wxson.sort.node;

import cn.wxson.sort.comparator.AbstractComparator;

/**
 * Title 虚拟尾节点
 * 因为是最后一个节点,所以,不需要做任务传递操作,永远排在链表最后一位
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
public final class DummyTailNode<T> extends AbstractNode<T> implements AbstractComparator<T> {

    /**
     * 获取数据比较器
     *
     * @return 比较器对象
     */
    @Override
    protected AbstractComparator<T> comparator() {
        return this;
    }

    /**
     * 比较方法
     * 尾节点永远排在最后一位
     *
     * @param one 节点一
     * @param two 节点二
     * @return 比较结果
     */
    @Override
    public boolean compare(AbstractNode<T> one, AbstractNode<T> two) {
        return true;
    }
}

2.4 普通节点

普通节点将接收用户自定义比较器进行数据比较。

package cn.wxson.sort.node;

import cn.wxson.sort.comparator.AbstractComparator;

/**
 * Title 普通节点
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
public class CommonNode<T> extends AbstractNode<T> {

    /**
     * 比较器
     * 是普通节点必须的比较工具
     */
    private AbstractComparator<T> comparator;

    /**
     * 带参构造
     *
     * @param data 数据
     */
    public CommonNode(T data) {
        super(data);
    }

    /**
     * 注册比较器
     *
     * @param comparator 比较器
     */
    public void register(AbstractComparator<T> comparator) {
        this.comparator = comparator;
    }

    /**
     * 获取数据比较器
     *
     * @return 比较器对象
     */
    @Override
    protected AbstractComparator<T> comparator() {
        return this.comparator;
    }
}

3. 链表

3.1 链表结构抽象类

链表结构抽象类中存在虚拟头节点和虚拟尾节点,并实现链表所有遍历功能。

package cn.wxson.sort.biz;

import cn.wxson.sort.node.AbstractNode;
import cn.wxson.sort.node.DummyHeadNode;
import cn.wxson.sort.node.DummyTailNode;
import com.google.common.collect.Lists;

import java.util.List;

/**
 * Title 链表结构抽象类
 * 做初始化链表、表元素遍历等操作
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
public class AbstractLinkedList<T> {

    /**
     * 虚拟头节点
     */
    protected final AbstractNode<T> dummyHeadNode;
    /**
     * 虚拟尾节点
     */
    protected final AbstractNode<T> dummyTailNode;

    /**
     * 无参构造
     * 初始化链表的头尾虚拟节点
     */
    public AbstractLinkedList() {
        // 创建虚拟头节点、虚拟尾节点,并将它们关联起来
        this.dummyHeadNode = new DummyHeadNode<>();
        this.dummyTailNode = new DummyTailNode<>();
        this.dummyHeadNode.setNext(this.dummyTailNode);
        this.dummyTailNode.setPre(this.dummyHeadNode);
    }

    /**
     * 除虚拟头节点、虚拟尾节点外,是否包含其他节点
     *
     * @return 判定结果
     */
    public boolean hasNext() {
        return this.dummyHeadNode.getNext() != this.dummyTailNode;
    }

    /**
     * 获取链表元素
     *
     * @return 元素集合
     */
    public List<T> list() {
        List<T> result = Lists.newLinkedList();
        AbstractNode<T> pos = this.dummyHeadNode.getNext();
        while (pos != this.dummyTailNode) {
            result.add(pos.getT());
            pos = pos.getNext();
        }
        return result;
    }

    /**
     * toString方法
     *
     * @return 字符串
     */
    @Override
    public String toString() {
        // 不存在元素时,返回空集合
        if (!hasNext()) {
            return "[]";
        }
        // 存在元素时,逐个打印
        StringBuilder sb = new StringBuilder("[");
        AbstractNode<T> pos = this.dummyHeadNode.getNext();
        while (pos != this.dummyTailNode) {
            sb.append(pos.getT().toString()).append(",");
            pos = pos.getNext();
        }
        String result = sb.substring(0, sb.lastIndexOf(","));
        return result + "]";
    }
}

3.2 链表结构类

链表结构类中,在新增元素时,注册比较器,进行比较后,实现实时插入操作。

package cn.wxson.sort.biz;

import cn.wxson.sort.comparator.AbstractComparator;
import cn.wxson.sort.node.AbstractNode;
import cn.wxson.sort.node.CommonNode;

/**
 * Title 链表结构类
 * 功能:从头结点向后进行比较
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
public class LinkedList<T> extends AbstractLinkedList<T> {

    /**
     * 比较器
     */
    private final AbstractComparator<T> comparator;

    /**
     * 带参构造
     *
     * @param comparator 比较器
     */
    public LinkedList(AbstractComparator<T> comparator) {
        // 初始化链表
        super();
        // 注入比较器
        this.comparator = comparator;
    }

    /**
     * 新增元素
     *
     * @param data 数据
     */
    public void add(T data) {
        // 创建新节点,并注册比较器
        CommonNode<T> newNode = new CommonNode<>(data);
        newNode.register(this.comparator);
        // 从头节点开始,找到新节点应该插入的位置的下一个节点
        AbstractNode<T> next = dummyHeadNode.compareTo(newNode);
        // 将新节点插入链表
        AbstractNode<T> pre = next.getPre();
        newNode.setPre(pre);
        newNode.setNext(next);
        pre.setNext(newNode);
        next.setPre(newNode);
    }
}

4. 测试

我们新建几个用户类,来根据用户年龄进行实时排序测试。

4.1 用户类

package cn.wxson.sort.test;

import com.alibaba.fastjson.JSON;
import lombok.Builder;
import lombok.Getter;
import lombok.Setter;

/**
 * Title 用户类
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
@Getter
@Setter
@Builder
public class User {

    private String name;
    private int age;

    @Override
    public String toString() {
        return JSON.toJSONString(this);
    }
}

4.2 测试类

package cn.wxson.sort.test;

import cn.wxson.sort.biz.LinkedList;
import lombok.extern.slf4j.Slf4j;

/**
 * Title 测试类
 *
 * @author Ason(18078490)
 * @date 2020-08-03
 */
@Slf4j
public class Domain {

    public static void main(String[] arg) {
        // 创建三个用户
        User tom = User.builder().name("Tom").age(20).build();
        User kate = User.builder().name("kate").age(18).build();
        User jerry = User.builder().name("Jerry").age(22).build();
        // 创建链表,放入按照用户年龄升序排列的比较器
        LinkedList<User> linkedList = new LinkedList<>((one, two) -> one.getT().getAge() >= two.getT().getAge());
        log.info("链表初始化:{}", linkedList.toString());
        linkedList.add(tom);
        log.info("接收到第一个用户:Tom,{}", linkedList.toString());
        linkedList.add(kate);
        log.info("接收到第一个用户:Kate,{}", linkedList.toString());
        linkedList.add(jerry);
        log.info("接收到第一个用户:Jerry,{}", linkedList.toString());
    }
}

执行以上测试样例,我们来看下每次插入新数据后,链表结构:

实时插入排序算法插图(1)

通过上面结果,我们可以看到,实时插入效果已经实现!

总结

本篇文章通过链表结构实现了实时插入排序的功能,它的时间复杂度为O(n),排序执行时间,随着数据量递增。

这篇文章数据结构与我之前的一篇博文(基于队列模型编写一个入岗检查站)是相通的,学习后,希望对你有帮助!

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 实时插入排序算法

发表评论

免登录下载网,提供全网最优质的资源集合!