java - Java 中 int 数组链表的 bubbleSort()

Question

我在使用 bubbleSort 方法来完成我的非常独特的家庭作业时遇到了问题。

我们应该使用我们选择的排序方法来排序，得到这个 int 数组的链接列表。不是ArrayList，不仅仅是LinkedList。它的工作方式类似于链表，但每个节点包含一个容量为 10 个整数的数组。

我被排序方法困住了。我选择bubbleSort只是因为它在上次作业中使用过并且我感觉最熟悉它。任何有关尝试更好的排序方法的提示也将被认为是有帮助的。

这是我的代码:

public void bubbleSort() {

        current = head;                     // Start at the head ArrayNode
        for (int i = 0; i < size; i++) {    // iterate through each ArrayNode
            currentArray = current.getArray();  // get the array in this ArrayNode

            int in, out;    
            for (out = size-1; out > 1; out--) {        // outer loop (backwards)
                for (in = 0; in < out; in++) {              // inner loop (forwards)
                    if (currentArray[in] > currentArray[in+1])  // out of order?
                    swap(in, in+1);                             // swap them!
                }
            }
            current.setArray(currentArray);
            current = current.getNext();
        }
    }// End bubbleSort() method

// A helper method for the bubble sort
private void swap(int one, int two) {
    int temp = currentArray[one];
    currentArray[one] = currentArray[two];
    currentArray[two] = temp;
} // End swap() method

这是我应该做的事情的图片示例。

Answer 1

我找到了选择排序的解决方案。有几个测试值，运行一下就可以看到。 如果需要，我可以提供更多信息。

import java.util.ArrayList;
import java.util.Random;

public class ArrayedListSort {

int listsize = 5;  // how many nodes
int maxValue = 99; // the highest value (0 to this)
int nodeSize = 3;  // size for every node

public static void main(String[] args) {
    // run non static
    new ArrayedListSort().runTest();
}

/**
 * Log function.
 */
public void log(Object s) {
    System.out.println(s);
}
public void logNoBR(Object s) {
    System.out.print(s);
}

/**
 * Output of list we have.
 */
public void logMyList(ArrayList<ListNode> listNode, String name) {
    log("=== LOG OUTPUT " + name + " ===");
    for ( int i=0; i < listNode.size(); i++) {
        logNoBR(" node <" + i + ">");
        logNoBR(" (");
        for (int j=0; j < listNode.get(i).getSize(); j++) {
            if ( j != (listNode.get(i).getSize()-1)) // if not last add ","
                logNoBR( listNode.get(i).getValueAt(j) + "," );
            else
                logNoBR( listNode.get(i).getValueAt(j) );
        }
        log(")");
    }
    log("=====================================\n");
}

public void runTest() {
    // create example List

    ArrayList<ListNode> myList = new ArrayList<ListNode>();

    // fill the nodes with random values
    for ( int i = 0; i < listsize; i++) {
        myList.add(new ListNode(nodeSize));
        for (int j=0; j < nodeSize; j++) {
            int randomValue = new Random().nextInt(maxValue);
            myList.get(i).addValue(randomValue);
        }
    }
    logMyList(myList, "myList unsorted"); // to see what we have

    // now lets sort it
    myList = sortListNode(myList);

    logMyList(myList, "myList sorted"); // what we have after sorting
}

/**
 *  Selectionsort 
 */
public ArrayList<ListNode> sortListNode(ArrayList<ListNode> myList) {
    ArrayList<ListNode> retList = new ArrayList<ListNode>();
    for ( int i = 0; i < listsize; i++) {
        retList.add(new ListNode(nodeSize));
    }
    int lastSmallest = myList.get(0).getValueAt(0);

    while ( !myList.isEmpty() ) {
        int lastJ=0, lastI=0;
        for ( int i = 0; i < myList.size(); i++) {
            for (int j=0; j < myList.get(i).getSize(); j++) {
                if ( myList.get(i).getValueAt(j) <= lastSmallest ) {
                    lastSmallest = myList.get(i).getValueAt(j);
                    lastJ = j;
                    lastI = i;
                    //log("Found smallest element at <"+i+","+j+"> (" + lastSmallest + ")");
                }
            }
        }
        myList.get(lastI).removeValue(lastJ);

        if ( myList.get(lastI).getSize() == 0 )
            myList.remove(lastI);

        // add value to new list
        for ( int i = 0; i < listsize; i++) {
            if ( retList.get(i).getSize() < retList.get(i).getMaxSize() ) {
                retList.get(i).addValue(lastSmallest);
                break;
            }
        }
        lastSmallest = Integer.MAX_VALUE;

    }
    return retList;
}

public class ListNode {
    private ArrayList<Integer>  values  = new ArrayList<Integer>();
    private  int                    maxSize;

    public ListNode(int maxSize) {
        this.maxSize = maxSize;
    }
    public ArrayList<Integer> getValues() {
        return values;
    }
    public int getMaxSize() {
        return maxSize;
    }
    public int getSize() {
        return values.size();
    }
    public int getValueAt(int position) {
        if ( position < values.size())
            return values.get(position);
        else
            throw new IndexOutOfBoundsException();
    }
    public void addValue(int value) {
        values.add(value);
    }
    public void removeValue(int position) {
        if ( position < values.size()) {
            values.remove(position);                    
        } else
            throw new IndexOutOfBoundsException();
    }
}

}