#java #insertion-sort
#java #вставка-сортировка
Вопрос:
Мне нужно заставить эту функцию сортировки вставки по существу копировать элементы вправо до тех пор, пока значение, которое необходимо переместить, не окажется в правильном положении, однако с кодом, который я использую, я обычно в конечном итоге удаляю мусор и попробовал несколько итераций с тем же результатом. Я в тупике, поскольку не вижу причин, по которым это не должно работать.
public static void Sort(Comparable[] a) {
int n = a.length;
Comparable temp = 0;
int x;
// Starting with the element at index 1...
for (int i = 1; i < n; i ) {
// ...move to the left until we find one less
// than the current element.
for (int j = i; j > 0; j--) {
if (less(a[j], a[j - 1]))
{
temp = a[j];
for(x = j; x > 0 amp;amp; less(temp, a[x]); x--)
{
a[x] = a[x - 1];
}
a[x] = temp;
//exch(a, j, j - 1);
}
else
break;
}
}
}
кстати, less(a, b) проверяет, является ли a < b.
Комментарии:
1. эй, внутренний цикл должен идти до нуля, и не нужно проверять i, это было бы как
for (int j = i-1;j>=0;j--)2. Я думаю, что ваш внутренний цикл for (
for x = j;...) буквально перезаписывает весь массив начальным значением. Начните с этого. Почему ваша логика настолько сложна с итерацией вперед, затем назад, затем снова назад с некоторыми другими странными вызовами? Попробуйте упростить, посмотрите алгоритм сортировки вставкой. Это не так сложно.
Ответ №1:
На первой итерации самого внутреннего цикла в этом условии: x > 0 amp;amp; less(temp, a[x]) вы проверяете, является ли значение, которое вы только что сохранили в temp …, меньше, чем значение, которое вы только что сохранили в temp, на которое ссылается другое имя. Это всегда будет возвращать false, в результате чего цикл никогда не запустится. Конечным результатом является то, что весь метод является дорогостоящим безоперационным. Если вы тестируете это, отправляя случайно перемешанный массив, в конечном итоге массив по-прежнему будет случайным образом перемешан, когда это будет сделано.
Чтобы исправить это, просто вычтите 1 из индекса в этом условии, получив его x > 0 amp;amp; less(temp, a[x - 1]) .
Я думаю, что остальная часть вашего кода выглядит корректно, хотя цикл с j избыточен и может быть удален.
Ответ №2:
Это должно сработать
public static void Sort(Comparable[] a) {
int n = a.length;
Comparable temp = 0;
int x;
// Starting with the element at index 1...
for (int i = 1; i < n; i ) {
// ...move to the left until we find one less
// than the current element.
for (int j = i; j > 0; j--) {
if (less(a[j], a[j - 1]))
{
temp = a[j];
for(x = j; x > 0 amp;amp; less(temp, a[x-1]); x--)
{
a[x] = a[x - 1];
}
a[x] = temp;
//exch(a, j, j - 1);
}
else
break;
}
}
}