链表上的冒泡排序实现

我必须在链接列表而不是数组上实现BubbleSort算法。 我是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所以它会按升序对Object名称进行排序。

 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(); } } 

Answer 1

在列表中，有一个大小字段有助于存储列表中的元素数量。 同时使SinglyNode implement Comparable类SinglyNode implement 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); } 

Answer 2

您需要在SinglyNode中实现Comparable接口，并在实现中使用字符串比较方法。 就像是：

 public void compareTo(SinglyNode node){ return this.names.toString.compareTo(node.getNames().toString()); } 

或者更好的只是this.names.compareTo(node.getNames());

但是，我不会只使用Object类，而是使用Comparable接口来处理那些通配符对象。

Answer 3

既然是作业/作业，我会给出一个提示，而不是直接的解决方案。 冒泡排序可以抽象为这两个操作：迭代集合和交换元素。 这些操作以数组或链表的forms实现，但算法是相同的。 你有迭代display ，现在你需要实现交换然后做（非常抽象的伪代码：

 iterate { iterate { if el.Compare(elNext) > 0 { swap(el, el.Next); } } } 

Answer 4

1）您需要实现Comparable

2）您还需要在bubblesort中使用swap方法。 目前您没有使用它，它只会比较两个对象而不在实际列表中交换它们。

使用Comparable的教程

Answer 5

示例链接列表冒泡排序不使用elementAt（）函数模拟随机访问，而是通过节点之间的链接进行操作，因此时间复杂度为O（n ^ 2）而不是更糟。 “end”用于跟踪列表末尾的排序节点的开始位置。 我使用了问题中的示例代码，并且没有将类更改为可比较，使用toString（）代替比较。 我使用了一个虚拟节点来简化代码。

 void bubbleSort() { if(first == null) return; SinglyNode dmy = new SinglyNode("dummy"); // dummy node dmy.next = first; // end == null or first sorted node at end of list SinglyNode end = null; int swap; do{ swap = 0; SinglyNode prv = dmy; // previous node while(true){ SinglyNode cur = prv.next; // current node SinglyNode nxt = cur.next; // next node if(nxt == end){ // if at end node end = cur; // update end = cur break; // and break } // if out of order, swap nodes if(cur.names.toString().compareTo(nxt.names.toString()) > 0){ cur.next = nxt.next; nxt.next = cur; prv.next = nxt; swap = 1; } prv = prv.next; // advance to next node } }while(swap != 0); // repeat untl no swaps first = dmy.next; // update first } 

Answer 6

对于冒泡排序，两个循环必须从0开始。该算法的某些版本在外循环所在的位置启动内循环。 这样做会导致某些数据出现问题。

如果……您有一个包含以下要排序的数组：

23,3,1,2,3,4,5

如果两个循环从0开始，则排序数组将是：1,2,3,3,4,5,23

但是如果内部循环从j = i开始，则排序的数组将是23,1,2,3,3,4,5。这是因为内部循环从第一个元素（将是3）后面移动把23放在正确的位置，永远不知道在哪里放置3