Упражнения на Java: алгоритм CombSort
Алгоритм сортировки Java: упражнение 11 с решением
Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма CombSort.
Расческа - это разновидность пузырчатой сортировки. Подобно сортировке «Шелл», сортировка «Гребень» увеличивает разрыв, используемый в сравнениях и обменах. Некоторые реализации используют сортировку вставкой, когда зазор меньше определенной величины. Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка не представляют проблемы при пузырьковой сортировке.
В пузырьковой сортировке, когда сравниваются любые два элемента, они всегда имеют разрыв 1. Основная идея гребенчатой сортировки состоит в том, что разрыв может быть намного больше 1.
Визуализация гребенчатой сортировки:
Анимационные кредиты: Jerejesse
Пример решения:
Java-код:
import java.util.Arrays;
class CombSort {
void CombSort(int nums[]){
int gap_length = nums.length;
float shrinkFactor = 1.3f;
boolean swapped = false;
while (gap_length > 1 || swapped) {
if (gap_length > 1) {
gap_length = (int)(gap_length / shrinkFactor);
}
swapped = false;
for (int i = 0; gap_length + i < nums.length; i++) {
if (nums[i] > nums[i + gap_length]) {
swap(nums, i, i + gap_length);
swapped = true;
}
}
}
}
private static void swap(int nums[], int x, int y) {
Integer temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
// Method to test above
public static void main(String args[])
{
CombSort ob = new CombSort();
int nums[] = {7, -5, 3, 2, 1, 0, 45};
System.out.println("Original Array:");
System.out.println(Arrays.toString(nums));
ob.CombSort(nums);
System.out.println("Sorted Array");
System.out.println(Arrays.toString(nums));
}
}
Пример вывода:
Оригинальный массив: [7, -5, 3, 2, 1, 0, 45] Сортированный массив [-5, 0, 1, 2, 3, 7, 45]
Блок - схема:
Редактор кода Java:
Внесите свой код и комментарии через Disqus.
Предыдущий: Напишите Java-программу для сортировки массива заданных целых чисел с использованием алгоритма сортировки Коктейля.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма CountingSort.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования