当前位置:编程学习 > JAVA >>

java单链表存储的冒泡排序算法

请各位大神给我一个标准的java单链表存储的冒泡排序算法,谢啦 --------------------编程问答--------------------

/**
 * 单向链表排序
 * @author 
 * @version May 17, 2013
 * @see LinkedCompositor
 * @since
 */
public class LinkedCompositor
{

    public static void main(String[] args)
    {
        //自定义链表头,头结点比较特殊,不参与排序
        MyLinkedUnit header = new MyLinkedUnit(-1, null);

        //初始化链表,在header之后初始化10个节点
        initLinkedUnits(header, 10);

        //打印生成的链表
        System.out.println("排序前的链表:" + header.getNext());

        //排序操作
        sortLinkedUnits(header);

        //打印冒泡排序后的链表
        System.out.println("排序后的链表:" + header.getNext());
    }

    /**
     * 冒泡排序链表
     * @param header 
     * @see
     */
    private static void sortLinkedUnits(MyLinkedUnit header)
    {
        MyLinkedUnit min;

        //用i、j方式,模仿传统冒泡排序
        for (MyLinkedUnit i = header.getNext(); i != null; i = i.getNext())
        {
            min = i;
            for (MyLinkedUnit j = i.getNext(); j != null; j = j.getNext())
            {
                //冒泡判断
                if (j.getValue() < min.getValue())
                {
                    min = j;
                }
            }

            //冒泡交换
            swap(header, i, min);

            //当前索引保持在最小节点索引处
            i = min;
        }
    }

    /**
     * 节点交换
     * @param header
     * @param current
     * @param min 
     * @see
     */
    private static void swap(MyLinkedUnit header, MyLinkedUnit current, MyLinkedUnit min)
    {
        //若待交换的为同一个节点,则不需要交换
        if (current == min)
        {
            return;
        }

        //current的前置节点
        MyLinkedUnit cCur = header;

        //min的前置节点
        MyLinkedUnit cMin = header;

        for (MyLinkedUnit p = header.getNext(); p != null; p = p.getNext())
        {
            //得到current的前置节点
            if (p.getNext() == current)
            {
                cCur = p;
            }

            //得到min的前置节点
            if (p.getNext() == min)
            {
                cMin = p;
            }
        }

        //辅助节点
        MyLinkedUnit temp = min.getNext();

        //待交换的两个节点相邻或不相邻,逻辑处理不同
        if (cMin == current)
        {
            min.setNext(current);
        }
        else
        {
            min.setNext(current.getNext());
            cMin.setNext(current);
        }
        current.setNext(temp);
        cCur.setNext(min);

    }

    /**
     * 初始化链表
     * @param header
     * @param size
     * @see
     */
    private static void initLinkedUnits(MyLinkedUnit header, int size)
    {
        //头节点索引副本
        MyLinkedUnit point = header;
        Random rd = new Random();

        MyLinkedUnit temp;
        for (; size > 0; size--)
        {
            //100以内随机整数
            temp = new MyLinkedUnit(rd.nextInt(100), null);
            point.setNext(temp);
            point = point.getNext();
        }
    }
}


/**
 * 自定义单链表
 * @author 
 * @version May 17, 2013
 * @see MyLinkedUnit
 * @since
 */
class MyLinkedUnit
{

    /**
     * 链表值
     */
    private int value;

    /**
     * 指向下一个链表节点
     */
    private MyLinkedUnit next = null;

    /**
     * 构造方法
     * @param value
     * @param myLinkedUnit
     */
    public MyLinkedUnit(int value, MyLinkedUnit myLinkedUnit)
    {
        this.value = value;
        this.next = myLinkedUnit;
    }

    public int getValue()
    {
        return value;
    }

    public MyLinkedUnit getNext()
    {
        return next;
    }

    public void setNext(MyLinkedUnit next)
    {
        this.next = next;
    }

    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        MyLinkedUnit temp = this;
        for (; temp != null; temp = temp.getNext())
        {
            sb.append("  " + temp.getValue());
        }

        return sb.toString();
    }
}
--------------------编程问答-------------------- 好勇敢的妹纸!!
补充:Java ,  Java相关
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,