java - 重复值插入排序，双向链表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'
}

我用 >= 替换了 > 以使循环在键大于 或等于 当前元素时立即停止。这样， key 将插入到相等值之后而不是之前。

我建议您扩展 insertBefore 以在 cursorPosition == 0 时在开头插入。这是一个逻辑扩展，消除了插入排序算法中的特殊情况。