java - Hashtable 中键迭代器排序的调试

Question

我正在做这个作业，它需要一个使用实现字典 ADT 接口(interface)的哈希表的电话簿。我的文件完全运行，没有任何错误，但只有一个缺点!我的哈希表中的键值未排序。当我查找具有特定数字组合的电话号码时，它们应该按排序顺序显示。

除了快速排序之外，我还尝试使用希尔排序，但它似乎没有帮助。这是我正在尝试的:

public class KeyIterator implements Iterator<K> {
    private DictionaryNode[] nodes, n;
    private int index;
    long modCheck;
    private DictionaryNode[] quickSort(DictionaryNode array[]){         
        n=array;
        quickSort(0, n.length-1);
        return n;

    }
    private void quickSort(int left, int right){
        if(right-left<=0)
            return;
        DictionaryNode pivot=n[right];
        int partition=getPartition(left,right, pivot);
        quickSort(left,partition-1);
        quickSort(partition+1,right);
    }

    private int getPartition(int left, int right, DictionaryNode pivot){
        int lPtr=left-1;
        int rPtr=right;
        for(;;){
            while(n[++lPtr].compareTo(pivot)<0);
            while(rPtr>0 && n[--rPtr].compareTo(pivot)>0);
            if(lPtr>=rPtr)
                break;
            else swap(lPtr, rPtr);
        }
        swap(lPtr, right);
        return lPtr;
    }

    private void swap(int lPtr1, int rPtr2) {
        DictionaryNode temp=n[lPtr1];
        n[lPtr1]=n[rPtr2];
        n[rPtr2]=temp;

    }
    public KeyIterator() {
        nodes = new DictionaryNode[currentSize];
        index = 0;
        modCheck=modCount;
        int j = 0;
        for (int i = 0; i < tableSize; i++){

            for (DictionaryNode n : list[i]) 
                nodes[j++] = n;
        }

         nodes = (DictionaryNode[]) quickSort(nodes);

    }

我不应该在代码中使用任何 JAVA API。

Answer 1

为了更轻松地进行调试，您应该修改循环中的前缀增量。它倾向于先增加计数器，然后调用数组元素，而算法并不打算这样做。

例如:

来自 while(n[++lPtr].compareTo(pivot)<0);

至

while(n[lPtr].compareTo(pivot)<0)
lPtr++;

同时更改if (;;)至while (rPtr <= lPrt)并摆脱

if(lPtr>=rPtr)
break;

它们只是让调试看起来很困惑。我希望你能发现一些改变。