对于我从事的一个项目，我的任务是为两种不同的搜索算法确定搜索时间：二分搜索和顺序搜索。对于每种算法，我都应该记录排序输入和未排序输入的时间。当我比较排序输入与未排序输入的顺序搜索的搜索时间时，我遇到了一些奇怪的事情。根据我首先排序的哪个，该搜索时间将明显大于第二个。因此，如果我首先对排序的进行顺序搜索，它将比对未排序的顺序搜索花费更长的时间。
这对我来说没有意义，也是我困惑的根源。确保在数据输入中找到搜索的键（通过顺序搜索），因为键是从输入中获取的。
这是产生问题的代码。在这种情况下，seqOnUnsorted 的搜索时间会比 seqOnSorted 长得多，这是不应该的。
public void sequentialSearchExperiment(){
seqOnUnsorted = sequentialSearchSet(keys, unsortedArray);
writeOutExperimentResults(seqOnUnsorted, seqOnUnsortedFilename, "Sequential Sort on Unsorted: ");
seqOnSorted = sequentialSearchSet(keys, sortedArray);
writeOutExperimentResults(seqOnSorted, seqOnSortedFilename, "Sequential Sort on Sorted: ");
}
sequenceSearchSet() 方法如下：
public SearchStats[] sequentialSearchSet(int[] keys, int[] toSearch){
SearchStats[] stats = new SearchStats[keys.length];
for (int i = 0; i < keys.length; i++){
stats[i] = sequentialSearch(keys[i], toSearch);
}
return stats;
}
这是顺序搜索（）：
public SearchStats sequentialSearch(int key, int[] toSearch){
long startTime = System.nanoTime(); // start timer
// step through array one-by-one until key found
for (int i = 0; i < toSearch.length; i++){
if (toSearch[i] == key){
return new SearchStats(key, i, System.nanoTime() - startTime);
}
}
// did not find key
return new SearchStats(key, -1, System.nanoTime() - startTime);
}
这是 SearchStats 构造函数：
public SearchStats(int keySearchedFor, int indexOfFound, long searchTime){
this.keySearchedFor = keySearchedFor;
this.indexOfFound = indexOfFound;
this.searchTime = searchTime;
}
如果我进行测试运行，我得到的平均搜索时间：
sequential search on sorted: 21,080 ns
sequential search on unsorted: 2,137,465 ns
如您所见，因为我先搜索未排序的，所以搜索时间明显更长。谁能解释为什么会这样？而且，我怎么能避免这种怪异呢？