冒泡（）在Java

Question

我有一個冒泡法爲我非常獨特家庭作業麻煩的int數組鏈表。

我們應該使用我們選擇的排序方法來排序，得到這個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

我們走吧。簡單的解決方案包括提取每個數組節點的所有元素，並將它們存儲在一個單獨的大數組中，對大數組進行排序（使用Bubble Sort，Quick Sort，Shell Sort等），最後重構帶有排序的值。我幾乎可以肯定，這不完全是你在找什麼。

如果要到位數字排序，我認爲以下算法：

正如其他人評論說，你需要確定一個比較函數，如果一個節點一個一個節點之前去B。下面的算法使用第一個想法，但是對於每對節點，例如A->[3, 9, 7]和B->[1, 6, 8]變成[1, 3, 6, 7, 8, 9]，最後是A->[1,3, 6]和B->[7, 8, 9]。如果我們對每個可能的對應用這種重新排列，最終會得到一個排序後的數組鏈表（儘管我沒有證據）。

A = head; 
while (A.hasNext()) { 
    arrayA = A.getArray(); 
    B = A.getNext(); 
    while (B.hasNext()) { 
     arrayB = B.getArray(); 

     // concatenate two arrays 
     int[] C = new int[arrayA.size() + arrayB.size()]; 
     int i; 
     for (i = 0; i < arrayA.size(); i++) 
      C[i] = arrayA[i]; 
     for (; i < arrayA.size() + arrayB.size(); i++) 
      C[i] = arrayB[i-arrayA.size()]; 

     // sort the new arrays using agains Bubble sort or any 
     // other method, or Arrays.sort() 
     Arrays.sort(C); 

     // now return the sorted values to the two arrays 
     for (i = 0; i < arrayA.size(); i++) 
      arrayA[i] = C[i]; 
     for (i = 0; i < arrayB.size(); i++) 
      arrayB[i] = C[i+arrayA.size()]; 
    } 
} 

這是一種僞代碼，因爲我沒有在Java中使用鏈表，但我認爲你有這個想法。

NOTE：我沒有測試過代碼，它可能包含恐怖。

Answer 2

我找到了selectionsort的解決方案。有幾個測試值，只需運行它即可看到它。 如果需要，我可以提供更多信息。

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(); 
    } 
} 

}