我必须在链表而不是数组上实现冒泡排序算法。我是java新手,所以我真的不知道如何将它放入代码中。但我尝试了一下,结果如下:
SinglyNode.java
public class SinglyNode
{
public Object names;
public SinglyNode next;
public SinglyNode (Object name1)
{
names = name1;
}
public SinglyNode (Object name2, SinglyNode next1)
{
names = name2;
next = next1;
}
Object getObject()
{
return names;
}
SinglyNode getNext()
{
return next;
}
void displayLink()
{
System.out.print("{" + names + "}");
}
}
LinkList.java 我认为我的问题出在方法中。我不知道如何实现 BubbleSort,以便它按升序对对象名称进行排序。
public class LinkList
{
SinglyNode first;
public boolean isEmpty()
{
return (first == null);
}
void insertFirst(Object name1)
{
SinglyNode newNode1 = new SinglyNode(name1);
newNode1.next = first;
first = newNode1;
}
SinglyNode delete(Object name2)
{
SinglyNode temp = first;
first = first.next;
return temp;
}
void display()
{
System.out.print("LIST: \n");
SinglyNode current = first;
while(current != null)
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("\n");
}
//////////////////////////////////////////////////////
void bubbleSort()
{
Object n = first;
Object temp = first;
if (na.compareTo(first) < first.compareTo(na))
{
temp = na.compareTo(first);
} else {
temp = first.compareTo(na);
}
System.out.println(temp);
}
private void swap(Object one, Object two)
{
Object temp = one.names;
one.names = two.names;
two.names = temp;
}
}
SinglyLinkList.java
public class SinglyLinkList
{
public static void main (String args[])
{
LinkList list = new LinkList();
list.insertFirst("Squirtle");
list.insertFirst("Bulbasaur");
list.insertFirst("Charmander");
list.insertFirst("Pichu");
list.insertFirst("Ghastly");
list.insertFirst("Mewtwo");
list.insertFirst("Dialga");
list.display();
list.bubbleSort();
list.display();
}
}
最佳答案
在列表中,有一个大小字段将有助于存储列表中的元素数量。还要使类 SinglyNode 实现 Comparable
,以便 compareTo
方法按照您的需要运行。 Single LinkedList中两个元素的就地交换其实相当复杂,而且性能非常糟糕!
public void bubbleSort
{
for (int i = 0; i < size; i++)
{
for (int j = i; j < size; j++)
{
if (elementAt(j).compareTo(elementAt(j+1)) > 0)
{
swap(j, j + 1);
}
}
}
}
public SinglyNode elementAt(int index)
{
SinglyNode temp = first;
for (int i = 0, i < index; i++)
{
temp = temp.getNext();
}
return temp;
}
public void swap(int firstIndex, int secondIndex)
{
SinglyNode secondNext = elementAt(secondIndex).getNext();
SinglyNode second = elementAt(secondIndex);
SinglyNode first = elementAt(first);
SinglyNode firstPrevious = elementAt(first - 1);
firstPrevious.setNext(second);
first.setNext(secondNext);
second.setNext(first);
}
关于java - 链表上的冒泡排序实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16033800/