Я учусь в классе APCS на старших курсах средней школы и учусь на промежуточных курсах.Мой учитель сказал, что ниже приведен оптимальный способ кодирования: «Сортировка по возрастанию - выберите правую ось, а при разбиении - сначала посмотрите на левую / Сортировка по убыванию - выберите левую ось, а при разборе - сначала на правую» *
СначалаЯ не мог понять, почему, поэтому я просто попробовал все случаи, которые я пробовал для сортировки по возрастанию
(1), выбирая правую ось / сначала смотря на левую *
(2), выбирая правильнуюповорот / взгляд вправо первым
(3) выбор левого вращения / взгляд сначала левым
(4) выбор левого поворота / взгляд сначала вправо
Но у меня есть только (1) тип для работы.В остальных 3 версиях есть логические ошибки.По своему опыту я знаю, что (2) ~ (4) сложнее кодировать. По опыту и написанию на бумаге я знаю, что, если я использую правильную ось и сначала смотрю на правую, возникнет проблема с использованием обычного способа быстрой сортировки.
Подвести итоги: ВОПРОСЫ [1] Какова точная причина, по которой версию (2) ~ (4) сложнее кодировать, чем (1)?[2] Может ли кто-нибудь из вас, замечательных программистов, помочь мне завершить (2) ~ (4)
вот код для версии (1), работающей в Java
///* MOST SIMPLE VERSION OF QUICKSORT. ASCENDING, END PIVOT, LEFT FIRST
SWEEP, LEFT & RIGHT COMPARISON
public static void endPivSortV1(int[] a, int start, int end) {
if(start < end) {
int pVal = a[end];
int left = start;
int right = end;
//QUESTION: right = end - 1
while(true) {
while(a[left] <= pVal && left < right) //left,
left++;
while(a[right] >= pVal && left < right)
right--;
if(left == right)
break;
swap(a, left, right);
}
swap(a, left, end);
endPivSortV1(a, start, left - 1);
endPivSortV1(a, left + 1, end);
}
} //*/
Я скопировал ивставил этот код и чуть-чуть изменил его для создания версий (2) ~ (4), но они не работают.
public static void endPivSortV2(int[] a, int start, int end) {
if(start < end) {
int pVal = a[end];
int left = start - 1;
int right = end + 1;
while(true) {
while(a[right--] >= pVal && left < right);
while(a[left++] <= pVal && left < right);
if(left == right)
break;
swap(a, left, right);
}
swap(a, left, end);
endPivSortV2(a, start, left - 1);
endPivSortV2(a, left + 1, end);
}
}
Именно здесь я пытаюсь сначала взглянуть на право, а не наоставил.(в то время как предложение об изменении права расположено перед тем, которое меняется слева), я знаю, что код очень неаккуратный и полон ошибок, но мне пришлось немного расслабиться, потому что я только частично кодировал неполный рабочий день в течение 1 года в старшей школе...
Спасибо.Это мой первый пост здесь, так что не жди меня: D