#java #arraylist #casting #quicksort
#java #список массивов #Кастинг #быстрая сортировка
Вопрос:
мой преподаватель предложил мне опубликовать мою проблему в stackover flow, потому что это не то, что мой профессор рассмотрел (он собирается осветить это). Тем не менее, это оценка. Я понимаю быструю сортировку, и остальная часть моей программы работает, но независимо от того, что я пытаюсь, моя быстрая сортировка не будет функционировать.
Это задание предназначено для того, чтобы мы могли самостоятельно практиковать использование generics. Наш профессор не научил нас, как это делается; он ожидает, что мы сами научимся. Я пробовал: compareTo, циклические операнды < и>. Пробовал читать учебник, но не нашел решения моей проблемы. Я также пытался работать со своими партнерами по проекту, но они отказались от курса и отказываются мне помогать. Это все еще оценка, поэтому я завершаю ее самостоятельно. Я просто опубликую соответствующую часть кода
public static <E extends Comparable> int partition(E[] list,int low, int high) {
E pivot = list[low];
int i = low - 1;
int j = high 1;
while (i < j)
{
for (i ; (int) list[i] < pivot i );
for (j--; (int) list[j] > pivot; j--);
if (i < j)
swap(i, j);
}
return j;
}
}
На выходе должен получиться отсортированный список из драйвера.
Комментарии:
1.
;завершает работу ваших тел цикла, так что у вас есть два пустых цикла for, а затем одинifвwhile. Кроме того, почему вы сравниваетеiиj? Вы платите своему преподавателю?2. Здравствуйте и добро пожаловать! Во-первых, «Это задание предназначено для того, чтобы мы могли самостоятельно практиковаться в использовании generics». похоже, что получение советов от преподавателя, работа в группе и публикация в StackOverflow противоречат цели задания. В любом случае, в чем собственно проблема, с которой вы столкнулись? «Это не будет функционировать» — это не совсем ясная постановка проблемы.
3. Вот руководство по стилю Java-кода, которое использовали мои различные работодатели: Необязательные фигурные скобки необязательны. То есть вы бы не сказали, что если (условие) вздор. Вы бы сказали, если (условие) { бла}. Хотя язык допускает одну строку для блока кода (if, for, while и т.д.), И исключить фигурные скобки проще простого, это открывает вам доступ к целому огромному классу ошибок программирования, которые могут быть незаметны. Итак, мы не рассматриваем необязательные фигурные скобки как необязательные, и в результате мы не сталкиваемся с этими странными классами ошибок.
4. Вы уже узнали о рекурсии? Я попытался найти хороший учебник, который вы могли бы использовать, но, похоже, все они используют рекурсию.
5. Я самостоятельно научился небольшой рекурсии. Я думаю, что понимаю.
Ответ №1:
Приведенный выше код похож на схему разделения Хоара. Выбор [low] для pivot будет наихудшим вариантом для уже отсортированных данных, и типичная схема Хоара будет бесконечно повторяться, если для pivot выбрано [high]. В одном из циклов for, похоже, отсутствует внутренняя точка с запятой. Ниже приведена типичная схема разделения Хоара.
public static <E extends Comparable> void quicksort(E[] list, int low, int high)
{
if(low >= high)
return;
int index = partition(list, low, high);
quicksort(list, low, index);
quicksort(list, index 1, high);
}
public static <E extends Comparable> int partition(E[] list, int low, int high)
{
E pivot = list[low (high-low)/2];
int i = low - 1;
int j = high 1;
while (true)
{
while(list[ i].compareTo(pivot) < 0);
while(list[--j].compareTo(pivot) > 0);
if(i >= j)
break;
E temp = list[i];
list[i] = list[j];
list[j] = temp;
}
return j;
}
Чтобы избежать переполнения стека для шаблонов данных наихудшего случая:
public static <E extends Comparable> void quicksort(E[] list, int low, int high)
{
while(low < high)
{
int index = partition(list, low, high);
if((index - low) <= (high - index)){
quicksort(list, low, index);
low = index 1;
} else {
quicksort(list, index 1, high);
high = index;
}
}
}