0
我已經寫了一個簡單的方法來將新元素添加到排序後的列表類中,代碼位於Dart中,但應該相當明顯,所有類似於C的語言都會發生什麼,我已經在其上運行了幾個簡單的單元測試而且它確實似乎以正確的順序添加了新的元素,我的問題是,它是完全證明嗎?它可以更有效率嗎?我試圖使用二進制搜索找到一個合適的索引處插入,也將返回新對象插入到索引:我的二分查找算法(a)正確嗎?(b)有效嗎?
int add(T obj){
int loIdx = 0;
int upIdx = list.length - 1;
int i;
while(loIdx <= upIdx){
i = loIdx + ((upIdx - loIdx) >> 1);
switch(_compare(obj, list[i])){
case 0:
loIdx = i;
upIdx = i - 1;
break;
case -1:
upIdx = i - 1;
if(loIdx == upIdx){
if(_compare(obj, list[loIdx]) == 1){
loIdx++;
}
}
break;
case 1:
loIdx = i + 1;
break;
}
}
list.insert(loIdx, obj);
return loIdx;
}
只是爲了完整性,這裏是進出口使用單元測試的一個顯示它的實際工作:
test('Order',(){
SortedList<int> intList = new SortedList<int>((int a, int b) => a.compareTo(b));
intList.add(5);
intList.add(7);
intList.add(0);
intList.add(3);
intList.add(6);
intList.add(9);
intList.add(1);
intList.add(2);
intList.add(8);
intList.add(5);
intList.add(4);
expect(intList.list, orderedEquals([0,1,2,3,4,5,5,6,7,8,9]));
});
這有什麼奇怪的約模運算符?這沒什麼特別的Dart ... – MarioP
@MarioP:我認爲彼得是正確的:你搜索的是中間索引,所以你應該使用整數除以2(〜/ 2)或者更快的移位(>> 1)。到目前爲止,您的算法每次只移動一個(甚至是0)索引,因此它是O(n^2),而不是O(ln(n))。另外,請注意開銷:對於小列表(例如<5甚至更多)indexOf或寫得很好的手動搜索會更快。 – GameAlchemist
@GameAlchemist對不起,我沒有真正看代碼本身 - 措辭讓我覺得它在語法上很古怪。我應該仔細閱讀。 – MarioP