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相关