java 链表上的冒泡排序实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16033800/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
bubble sort implementation on linked lists
提问by lmpgdn
I have to implement a BubbleSort algorithm on a Linked List instead of an array. I'm new to java so I don't really know how to put it in code. But I gave it a try and here's what I got:
我必须在链表而不是数组上实现 BubbleSort 算法。我是 Java 新手，所以我真的不知道如何将它放入代码中。但我试了一下，这就是我得到的：
SinglyNode.java
单节点.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.javaI think my problem is here in the method. I dunno how to implement the BubbleSort so it would sort the Object names in ascending order.
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
单链表.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();
}
}
回答by The Cat
In your list it will help to have a size field, to store the number of elements in the list. Also make the class SinglyNode implement Comparableso the compareTomethod behaves as you want. The in-place swapping of two elements in Single LinkedList is actually quite involved, and the performance is really bad!
在您的列表中，有一个 size 字段将有助于存储列表中的元素数量。还要创建类，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);
}
回答by rcgldr
Example linked list bubble sort that doesn't emulate random access using an elementAt() function, and instead operates via the links between nodes, so time complexity is O(n^2) instead of being much worse. "end" is used to keep track of where the sorted nodes at the end of the list begin. I used the example code from the question and didn't bother changing the class to comparable, using toString() instead for the compare. I used a dummy node to simplify the code.
示例链表冒泡排序不使用 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
}
回答by Rubén
You need to implement the Comparable interface in the SinglyNode and use the string compare method inside the implementation. Something like:
您需要在 SinglyNode 中实现 Comparable 接口并在实现中使用字符串比较方法。就像是：
public void compareTo(SinglyNode node){
return this.names.toString.compareTo(node.getNames().toString());
}
Or better just this.names.compareTo(node.getNames());
或者更好 this.names.compareTo(node.getNames());
However instead of just use Object class, I would the use Comparable interface for those wildcard objects.
但是，我不只是使用 Object 类，而是为那些通配符对象使用 Comparable 接口。
回答by Nidis
1) You need to implement Comparable
1) 你需要实现 Comparable
2) You also need to use the swap method in bubblesort. Currently you are not using this and it will only compare the two objects without swapping them in the actual list.
2）在冒泡排序中还需要用到swap方法。目前您没有使用它，它只会比较两个对象而不在实际列表中交换它们。
Use the tutorialfor the Comparable
使用Comparable的教程
回答by Andrey
Since it is homework/assignment, I will give a hint instead of direct solution. Bubble sort can be abstracted to this two operations: iteration over collection and swapping elements. Those operations are implemented differently with array or linked list, but the algoritm is the same. You have iteration in display, now you need to implement swapping then do (very abstract pseudocode:
既然是作业/作业，我就给个提示，而不是直接解决。冒泡排序可以抽象为这两个操作：集合迭代和交换元素。这些操作与数组或链表的实现不同，但算法是相同的。你有迭代display，现在你需要实现交换然后做（非常抽象的伪代码：
iterate {
iterate {
if el.Compare(elNext) > 0 {
swap(el, el.Next);
}
}
}
回答by Sesh
For bubble sort, both the loops must start from 0. Some versions of that algorithm start the inner loop at where the outer loop is. Doing so will cause issues for some data.
对于冒泡排序，两个循环都必须从 0 开始。该算法的某些版本从外循环所在的位置开始内循环。这样做会导致某些数据出现问题。
If ... you have an array with the following that you want sorted:
如果...您有一个数组，其中包含要排序的以下内容：
23,3,1,2,3,4,5
23,3,1,2,3,4,5
the sorted array if both loops start at 0 would be: 1, 2, 3, 3, 4, 5, 23
如果两个循环都从 0 开始，则排序后的数组将是：1, 2, 3, 3, 4, 5, 23
But if the inner loop starts at j=i, the sorted array would be 23, 1, 2, 3, 3, 4, 5. This is because the inner loop moves on from the first element (which will be 3) after it puts 23 in the correct place and never figures out where to place 3 anymore
但是如果内循环从 j=i 开始，排序后的数组将是 23, 1, 2, 3, 3, 4, 5. 这是因为内循环从它之后的第一个元素（将是 3）开始将 23 放在正确的位置，再也不会弄清楚将 3 放在哪里
