Может ли кто-нибудь объяснить мне, как работает сортировка элементов в Java?
Меня смущает комментарий "сортировка начинается". Может ли кто-нибудь мне это объяснить.
class endsly {
public static void main(String[] args) {
int num[] = { 55, 40, 80, 65, 71 };
int n= num.length;
System.out.println("Given list: ");
for (int i = 0; i < n; i++) {
System.out.println(" " + num[i]);
}
System.out.println("\n");
//sorting begins
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (num[i] < num[j]) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
System.out.println("Sorted list:");
for (int i = 0; i < n; i++) {
System.out.println(" " + num[i]);
}
System.out.println(" ");
}
}
Это похоже на пузырьковая сортировка, вы можете прочитать довольно хорошее описание в Википедии.
@ Turing85 Почти. В пузырьковой сортировке вы сравниваете соседние элементы. Но это очень близко.
Также обратите внимание, что ваш вопрос не о том, «как работают элементы сортировки в Java», а о том, как работает конкретный код. Arrays.sort или Collections.sort (которые вы обычно подразумеваете под «сортировкой элементов в Java») работают совершенно иначе.
Некоторые замечания по вашему коду: Имена классов всегда должны начинаться с заглавной буквы --- int num[] Пожалуйста, не делайте этого, скобки влияют на тип, поэтому записывайте их в тип: int[] num.
Не могли бы вы пояснить, чего вы не можете понять в этом фрагменте кода. Это отсортирует ваш массив в порядке убывания.
@ Turing85 Я думаю, это на самом деле сортировка по выбору
@KevinAnderson, это странная смесь. Сортировка выбора обычно выполняет только одну замену после выбора минимального элемента в несортированной части.
Ответы 2
Два вложенных цикла реализуют вариант алгоритма Выбор Сортировка с небольшим "поворотом" в конце.
- Отсортированная часть массива находится слева от
i, т.е. элементы от 0 включительно доi, исключая - Вложенный цикл обходит неотсортированную часть, заменяя все более мелкие элементы на
num[i]. - К концу вложенного цикла наименьший из несортированных элементов находится в
num[i]. - К концу внешнего цикла массив сортируется
Обратите внимание, что это отличается от «классической» сортировки выбора, при которой выбирается следующий наименьший элемент из несортированного массива, ничего не меняя местами, и выполняется один обмен в конце вложенного цикла. Традиционная реализация сортировки по выбору выглядела бы так:
for (int i = 0; i < n; i++) {
int minPos = i;
// Look for a position of the smallest element
for (int j = i + 1; j < n; j++) {
if (num[minPos] < num[j]) {
minPos = j;
}
}
// Perform the swap after the loop has ended
int temp = num[i];
num[i] = num[minPos];
num[minPos] = temp
}
Алгоритм, который вы опубликовали, - сортировка по выбору, где разрешено несколько свопов, но в обратном порядке (так что самые большие элементы помещаются в начало массива, а не самые маленькие). Общий алгоритм сортировки выбора (стандартная сортировка выбора, при которой наименьший элемент перемещается в начало массива) с несколькими перестановками:
for element i at 0 to n:
for element j at i to n:
if element at j is less than element at i:
swap element at i with element at j
Начиная с элемента 0, алгоритм находит наименьшее значение от индекса 0 до индекса n и помещает его в индекс 0. На следующей итерации алгоритм находит наименьшее значение от индекса 1 до n и помещает его в индекс 1. На следующей итерации алгоритм находит наименьшее значение от индекса 2 до n и помещает его в индекс 2. Этот алгоритм продолжается до последней итерации, которая находит наименьшее значение от индекса n - 1 до n и помещает его в индекс n.
В конкретном случае вашего алгоритма это не наименьшее значение, которое можно найти на каждой итерации, это наибольшее. Таким образом, после сортировки массива он упорядочивается от наибольшего до наименьшего значения. Для справки, условным условием в алгоритме сортировки является num[i] < num[j], но, возможно, будет проще читать это как num[j] > num[i], что означает, что элементы должны быть заменены, если элемент в j больше, чем элемент в i. Вы можете увидеть каждый шаг, демонстрируемый, изменяя свой код для печати значения массива на каждом шаге:
public static void main(String[] args) {
int num[] = { 55, 40, 80, 65, 71 };
int n= num.length;
System.out.println("Before sorting");
printArray(num);
System.out.println();
//sorting begins
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (num[i] < num[j]) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
System.out.print("Iteration i = " + i + ": ");
printArray(num);
}
System.out.println("\nAfter sorting");
printArray(num);
System.out.println();
}
private static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
System.out.println();
}
Выполнение этого кода приводит к следующему результату:
Before sorting
55 40 80 65 71
Iteration i = 0: 80 40 55 65 71
Iteration i = 1: 80 71 40 55 65
Iteration i = 2: 80 71 65 40 55
Iteration i = 3: 80 71 65 55 40
Iteration i = 4: 80 71 65 55 40
After sorting
80 71 65 55 40
Как видно из выходных данных, каждая итерация последовательно находит наибольшее значение и перемещает его вниз. Во время первой итерации 80 перемещается в индекс 0; во второй 71 перемещается в индекс 1; и так далее, пока не будут выполнены 5 итераций (соответствующих размеру num). Хотя может показаться, что итерация i = 4 потрачена впустую, это верно только для этого конкретного случая, поскольку последние два элемента уже отсортированы (когда 65 и 55 меняются местами в итерации i = 2).
В общем, рекомендуется пройти каждую итерацию алгоритма сортировки, чтобы увидеть, что алгоритм делает. Это также помогает определить сложность алгоритма. В этом случае используется набор вложенных циклов, где внешний цикл идет от 0 к n, а внутренний цикл идет от i (начиная с 0) к n. Это создает следующую сложность: п (п-1) (п-2) ... или О (n2). Например, предположим, что в массиве есть элементы 10; внутренний цикл первой итерации будет запускать 10 раза; внутренний цикл второй итерации будет запускать 9; и так далее. См. Анализ сложности сортировки выбора в Википедии для получения дополнительной информации.
Алгоритм в вопросе отличается от стандартной сортировки выбора тем, что стандартная сортировка выбора находит минимальный (или максимальный в данном случае) элемент от i до n и выполняет не более одного обмена в конце итерации. В этом случае вместо выполнения одной замены в конце каждый раз, когда обнаруживается минимальное (или максимальное) значение, замена выполняется немедленно, что может привести к более чем одной замене за итерацию. Это можно продемонстрировать, применив алгоритм для печати значений массива каждый раз, когда выполняется своп:
public static void main(String[] args) {
int num[] = { 55, 40, 80, 65, 71 };
int n= num.length;
System.out.println("Before sorting");
printArray(num);
System.out.println();
//sorting begins
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (num[i] < num[j]) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
System.out.print(" Swap performed:");
printArray(num);
}
}
System.out.print("Iteration i = " + i + ": ");
printArray(num);
}
System.out.println("\nAfter sorting");
printArray(num);
System.out.println();
}
private static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
System.out.println();
}
Это приводит к следующему выводу:
Before sorting
55 40 80 65 71
Swap performed: 80 40 55 65 71
Iteration i = 0: 80 40 55 65 71
Swap performed: 80 55 40 65 71
Swap performed: 80 65 40 55 71
Swap performed: 80 71 40 55 65
Iteration i = 1: 80 71 40 55 65
Swap performed: 80 71 55 40 65
Swap performed: 80 71 65 40 55
Iteration i = 2: 80 71 65 40 55
Swap performed: 80 71 65 55 40
Iteration i = 3: 80 71 65 55 40
Iteration i = 4: 80 71 65 55 40
After sorting
80 71 65 55 40