У меня есть действительно большой вектор, который хранит 100000 различных значений, от 0 до 50000. Они представляют собой цилиндры на жестком диске, и я хочу сортировать этот вектор по трем различным алгоритмам используется для планирования диска. До сих пор я считывал эти 100 000 значений из файла, сохранял их в векторе, а затем сортировал их по желаемому алгоритму (FCFS, SCAN, SSTF). Проблема в том, что это занимает слишком много времени, потому что я делаю это в наименее творческом пути возможным:Быстрый способ сортировки действительно большой вектор
public static Vector<Integer> sortSSTF(Vector<Integer> array){
Vector<Integer> positions = new Vector<Integer>(array);
Vector<Integer> return_array = new Vector<Integer>();
int current_pos = 0,minimum,final_pos;
while(positions.size() > 0){
minimum = 999999;
final_pos = current_pos;
for(int i=0 ; i < positions.size() ; i++){
//do some math
}
}
return_array.add(final_pos);
current_pos = final_pos;
positions.removeElement(final_pos);
}
return return_array;
}
Моей функция принимает вектор в качестве параметра, делает копию, делает некоторую математику, чтобы найти нужный элемент из скопированного массива и хранить его в другом массиве, то должен быть упорядочен в соответствии с выбранным алгоритмом. Но в массиве с N элементами он принимает N! итераций для завершения, что слишком много, так как код должен делать это как минимум 10 раз.
Вопрос в том, как я могу сделать эту сортировку более эффективной?
1. Почему вы используете 'Vector' вместо' ArrayList'? 2. Вы слышали о 'Collections.sort();'? – jlordo
«100000 различных значений, от 0 до 50000» [они не могут быть разными] (http://en.wikipedia.org/wiki/Pigeonhole_principle): если у вас есть 100K элементов и только 50K разных значений, по крайней мере одно значение будет повторяться. – dasblinkenlight
вам не следует использовать вектор, если вы не работаете на C++ – 0x90