0

我必须在链接列表而不是数组上实现 BubbleSort 算法。我是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.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; 
}
}

单链表.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();

}
}
4

6 回答 6

2

在您的列表中，有一个大小字段将有助于存储列表中元素的数量。还要创建类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);
}
于 2013-04-16T10:08:14.740 回答
0

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

iterate {
 iterate {
  if el.Compare(elNext) > 0 {
    swap(el, el.Next);
  }
 }
}
于 2013-04-16T09:57:13.183 回答
0

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

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

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

但是，我不只是使用 Object 类，而是对这些通配符对象使用 Comparable 接口。

于 2013-04-16T09:51:58.550 回答
0

1）您需要实现 Comparable

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

使用Comparable的教程

于 2013-04-16T09:55:49.900 回答
0

示例链表冒泡排序不使用 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
}
于 2017-02-21T00:54:56.810 回答
-1

对于冒泡排序，两个循环都必须从 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 放在哪里

于 2017-10-14T00:28:32.303 回答