插入重複值的情況下排序，雙向鏈表ADT

Question

我有一個奇怪的問題，我的插入排序在輸入尾部重複值的情況下。我遇到的最基本的情況是數組{A，A，A}。由於我正在跟蹤初始索引，因此我可以判斷這是不恰當的排序，因此存儲了不正確的索引，導致值丟失。這裏是插入排序的實現：

List A = new List(); 
    String[] inputArray = {"A","A","A","A"}; 
    String key; 
    int i, j; 
    //begin insertion sort 
    for (j = 1; j < inputArray.length; j++) { 
     i = j - 1; 
     key = inputArray[j]; 
     while (i >= 0) { 
      if (key.compareTo(inputArray[i]) > 0) { 
       break; 
      } 
      inputArray[i+1] = inputArray[i]; 
      A.moveTo(i+1); 
      //make sure we aren't trying to insert before first node 
      if (i > 0) { A.insertBefore(i); } 
      else { A.prepend(i); } 
      //remove node at cursor 
      A.delete(); 
      i--; 
      System.out.println("inner: "+ A); 
     } 
     inputArray[i+1] = key; 
     A.moveTo(i+1); 
     if (i >= 0) { A.insertBefore(j); System.out.println("insert: " + A);} 
     else { A.prepend(j); System.out.println("prepend: " + A);} 
     System.out.println("current cursor:" + A.getIndex()); 
     A.delete(); 
     System.out.println("outer: " + A); 
    } 

隨着println的，我在這我得到以下輸出：

inner: 0 0 2 3 
prepend: 1 0 0 2 3 
current cursor:1 
outer: 1 0 2 3 //works fine the first time 
inner: 1 0 1 3 
inner: 0 1 1 3 
prepend: 2 0 1 1 3 
current cursor:1 
outer: 2 1 1 3 //deletes the wrong value? Why? 
inner: 2 1 1 2 
inner: 2 1 1 2 
inner: 0 2 1 2 
prepend: 3 0 2 1 2 
current cursor:1 
outer: 3 2 1 2 

這裏是List類的相關部分：

class List { 

private class Node { 
    //Fields 

    int data; 
    Node next, previous; 
    //Constructor 

    Node(int data) { 
     this.data = data; 
     next = null; 
     previous = null; 
    } 

    public String toString() { 
     return String.valueOf(data); 
    } 
} 
//Fields 
private Node frontNode, backNode, cursorNode; 
private int totalSize, cursorPosition; 

//Constructor 
List() { 
    frontNode = backNode = cursorNode = null; 
    totalSize = 0; 
    cursorPosition = -1; 
} 

//length(): Returns number of elements in this list 
int length() { 
    return totalSize; 
} 

//getIndex: Returns the index of the cursor element in this list, or 
//returns -1 if the cursor element is undefined. 
int getIndex() { 
    return cursorPosition; 
} 
//prepend(int data): Inserts new element before front element in this List. 
void prepend(int data) { 
    Node node = new Node(data); 
    if (this.length() == 0) { 
     frontNode = backNode = node; 
    } else { 
     frontNode.previous = node; 
     node.next = frontNode; 
     frontNode = node; 
    } 
    totalSize++; 
    if (cursorPosition != -1) { 
     cursorPosition++; 
    } 
} 

//insertBefore(int data): Inserts new element before cursor element in this 
// List. Pre: length()>0, getIndex()>=0 
void insertBefore(int data) { 
    Node node = new Node(data); 
    if (this.length() > 0 && this.getIndex() >= 0) { 
     node.previous = cursorNode.previous; 
     node.next = cursorNode; 
     cursorNode.previous.next = node; 
     cursorNode.previous = node; 
     totalSize++; 
     cursorPosition++; 
    } else if (this.length() <= 0) { 
     throw new RuntimeException("Error: insertBefore called on empty list"); 
    } else { 
     throw new RuntimeException("Error: insertBefore called without cursor set"); 
    } 
} 

Answer 1

無需修改while循環內的列表。

for (j = 1; j < inputArray.length; j++) { 
    i = j - 1; 
    key = inputArray[j]; 
    while (i >= 0) { 
     if (key.compareTo(inputArray[i]) >= 0) { 
      break; 
     } 
     inputArray[i+1] = inputArray[i]; 
     i--; 
    } 
    inputArray[i+1] = key; 
    A.moveTo(i+1); 
    A.insertBefore(j); // insert 'key' in right place 
    A.moveTo(j+1); 
    A.delete(); // remove old occurrence of 'key' 
} 

我換成>與>=使環路很快停止爲重點大於或等於當前元素。這樣鍵將在相同的值之後而不是之前插入。

我建議你在cursorPosition == 0的開頭插入insertBefore。這是一個邏輯擴展，它消除了插入排序算法中的特殊情況。