我正在处理此任务，该任务需要使用Hashtable的电话簿，该电话簿实现了Dictionary ADT接口。
我的文件完全正常运行，没有任何错误，但只有一个缺点！我的哈希表中的键值未得到排序。当我查找带有特定数字组合的电话号码时，应按排序顺序显示它们。
除此quicksort外，我还尝试使用shell sort，但似乎无济于事。
这是我正在尝试的：
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。
最佳答案
为了简化调试，您应该在循环中修改前缀增量。它倾向于先递增计数器，然后调用数组元素，而算法不打算这样做。
例如：
从
while(n[++lPtr].compareTo(pivot)<0);
至while(n[lPtr].compareTo(pivot)<0) lPtr++;
同时将if (;;)更改为while (rPtr <= lPrt)并摆脱if(lPtr>=rPtr) break;
他们只是使调试似乎混乱。我希望您可以对此进行一些更改。