1

我正在处理这个任务，它想要一个使用实现 Dictionary ADT 接口的 Hashtable 的电话簿。我的文件完全没有任何错误，但只有一个缺点！我来自哈希表的键值没有得到排序。当我查找具有特定数字组合的电话号码时，它们应该按排序顺序显示。

除了这个快速排序，我还尝试使用 shell 排序，但它似乎没有帮助。这是我正在尝试的：

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。

4

1 回答 1

0

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

例如：

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

至

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

也改掉if (;;)_while (rPtr <= lPrt)

if(lPtr>=rPtr) break;

他们只是让调试看起来很混乱。我希望你能找到一些改变。

于 2012-12-02T05:57:02.407 回答