我有一个冒泡排序,可用于根据文件中的数据创建的链接列表。如果数字小于起始头节点,我的排序算法将不起作用。如何更新代码以解决此问题?
示例:如果我的列表是3、1、8、5它将打印3-> 5-> 8,而1则无处可见
public void bubbleSort(LinkedNode head) {
LinkedNode previous;
LinkedNode current;
LinkedNode next;
boolean isSorted = true;
//if list is empty or only 1 item is in list -> it is sorted
if (head == null || head.getNext() == null) {
return;
}
long start = System.currentTimeMillis(); //begin count for bubbleSort
while(isSorted) {
bubbleComparisons = 0;
bubbleExchanges = 0;
previous = null;
current = head;
next = head.getNext();
isSorted = false;
while(next != null) {
bubbleComparisons ++; //increment counter for each comparison made
if (current.getElement() > next.getElement()) {
if (head == current) {
head = next;
}
else {
previous.setNext(next);
}
current.setNext(next.getNext());
next.setNext(current);
isSorted = true;
current = next;
bubbleExchanges++;
}
previous = current;
current = previous.getNext();
next = current.getNext();
}
更新代码的夫妇。我已经用// Up标记了它们。我运行了几个测试用例,只需检查它是否可以解决目的。
public class Solution {
static class LinkedNode {
private int element;
private LinkedNode next;
LinkedNode(int element) {
this.element = element;
}
public int getElement() {
return element;
}
public void setElement(int element) {
this.element = element;
}
public LinkedNode getNext() {
return next;
}
public void setNext(LinkedNode next) {
this.next = next;
}
}
private int bubbleComparisons;
private int bubbleExchanges;
public LinkedNode bubbleSort(LinkedNode head) {
LinkedNode previous;
LinkedNode current;
LinkedNode next;
boolean isSorted = true;
// if list is empty or only 1 item is in list -> it is sorted
if (head == null) {
return null;
} else if (head.getNext() == null) {
return head;
}
while (isSorted) {
// bubbleComparisons = 0; // Up - 08
// bubbleExchanges = 0; // Up - 09
previous = null;
current = head;
next = head.getNext();
isSorted = false;
while (next != null) {
bubbleComparisons++; // increment counter for each comparison made
if (current.getElement() > next.getElement()) {
if (head == current) {
head = next;
} else {
previous.setNext(next);
}
current.setNext(next.getNext());
next.setNext(current);
isSorted = true;
previous = next; // Up - 01
// current = next; // Up - 02
next = current.next; // Up - 03
bubbleExchanges++;
} else { // Up - 06
previous = current;
current = current.getNext(); // Up - 10 not required
next = current.getNext();
}
}
}
return head; // Up - 05
}
public static void main(String[] args) {
LinkedNode head = new LinkedNode(10);
head.setNext(new LinkedNode(8));
head.getNext().setNext(new LinkedNode(7));
head.getNext().getNext().setNext(new LinkedNode(5));
LinkedNode current = head;
while (current != null) {
System.out.print(current.element + "->");
current = current.next;
}
System.out.println();
Solution s = new Solution();
current = s.bubbleSort(head);
while (current != null) {
System.out.print(current.element + "->");
current = current.next;
}
System.out.println();
System.out.println("comp:" + s.bubbleComparisons);
System.out.println("exh:" + s.bubbleExchanges);
}
}