我应该使用优先级队列中的链表来实现插入排序方法。我的问题是,当对最后几个元素进行排序时,它会比较它们,但将它们放在错误的顺序中。这是我的代码。
PQInsertionSort 类
class PQInsertionSort
{
Entry head;
int size;
public PQInsertionSort()
{
head = null;
size = 0;
}
public void insert(Entry elem)
{
if (size == 0)
{
System.out.println("1");
head = elem;
}
else if(head.getKey() > elem.getKey())
{
System.out.println("2");
elem.setNext(head);
head = elem;
}
else
{
Entry curr;
Entry prev;
curr = head;
prev = head;
System.out.println("3");
while(curr.getNext() != null && curr.getKey() < elem.getKey())
{
prev = curr;
curr=curr.getNext();
System.out.println("curr is "+ curr.getKey() + " elem is " +elem.getKey());
}
if(curr.getNext() != null)
{
System.out.println("6");
elem.setNext(prev.getNext());
prev.setNext(elem);
}
else
{
System.out.println("5");
curr.setNext(elem);
}
}
size++;
}
public Entry removeMin()
{
Entry tmp = null;
if (size == 0)
{
System.out.println("Queue is empty.");
}
else
{
tmp = head;
head = head.getNext();
size--;
}
if (size == 0)
{
head = null;
}
return tmp;
}
public String min()
{
return head.getName();
}
public int size()
{
return size();
}
public boolean isEmpty()
{
return (head == null);
}
public void print()
{
Entry p = head;
while(p != null)
{
System.out.println(p.getKey() + p.getName());
p = p.getNext();
}
}
}
入门级
class Entry
{
private int key;
private String name;
private Entry next;
public Entry(int k, String n, Entry e)
{
key = k;
name = n;
next = e;
}
public void setNext(Entry e)
{
next = e;
}
public Entry getNext()
{
return next;
}
public int getKey()
{
return key;
}
public void setKey(int k)
{
key = k;
}
public String getName()
{
return name;
}
public void setName(String n)
{
name = n;
}
}
测试员类
public class Test {
public static void main(String[] args)
{
PQInsertionSort qs = new PQInsertionSort();
qs.insert(new Entry(4, "Sam", null));
qs.insert(new Entry(3, "Tim", null));
qs.insert(new Entry(7, "Amanda", null));
qs.insert(new Entry(1, "Chris", null));
qs.insert(new Entry(2, "Jimbo", null));
qs.insert(new Entry(5, "Melinda", null));
qs.insert(new Entry(6, "Alice", null));
qs.print();
}
}
输出是这样的
1
2
3
prev is 4 elem is 7
5
2
3
prev is 3 elem is 2
6
3
prev is 2 elem is 5
prev is 3 elem is 5
prev is 4 elem is 5
prev is 7 elem is 5
5
3
prev is 2 elem is 6
prev is 3 elem is 6
prev is 4 elem is 6
prev is 7 elem is 6
6
1Chris
2Jimbo
3Tim
4Sam
6Alice
7Amanda
5Melinda
看看 5 是如何作为 lass elem 输出的。有什么想法吗?
最佳答案
我似乎明白了。在 while 循环之后,我必须添加另一个条件,因为它直接传递到 else。所以应该是这样的。
if(curr.getNext() != null)
{
System.out.println("6");
elem.setNext(prev.getNext());
prev.setNext(elem);
}
else if(curr.getKey() > elem.getKey())
{
elem.setNext(prev.getNext());
prev.setNext(elem);
}
else
{
System.out.println("5");
curr.setNext(elem);
}
}
关于java - 优先级队列插入排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25349944/