Упражнения на Java: алгоритм сортировки кучи

Алгоритм сортировки Java: упражнение 5 с решением

Напишите Java-программу для сортировки массива заданных целых чисел с использованием алгоритма сортировки кучи.

В информатике, heapsort (изобретенный JWJ Williams в 1964 году) является алгоритмом сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит свои входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, выделяя самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не линейного поиска времени, чтобы найти максимум. Хотя на некоторых машинах он работает несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществом более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort - это алгоритм на месте, но он не является стабильным.

Запуск алгоритма heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой кратко показана древовидная структура кучи для иллюстрации.

Анимационные кредиты: RolandH

Пример решения:

Java-код:

import java.util.Arrays;
public class HeapSort {
    void HeapSort(int nums[]){
		buildheap(nums);
		for (int i = nums.length - 1; i >= 0; i--) {
			exchange(nums, i, 0);
			heap(nums, i, 0);
		}
	}
	private void exchange(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
	private void heap(int[] nums, int size, int i) {
		int left = ((2 * i) + 1);  
		int right = ((2 * i) + 2);
		int max = i;
		if ((left < size) && (nums[left] > nums[i])) {
			max = left;
		}
		
		if ((right < size) && (nums[right] > nums[max])) {
			max = right;
		}
		if (max != i) {
			exchange(nums, i, max);
			heap(nums, size, max);
		}
	}
	private void buildheap(int[] nums) {
		for (int i = (nums.length / 2) - 1; i >= 0; i--) {
			heap(nums, (nums.length - 1), i);
		}
	}
	// Method to test above
    public static void main(String args[])
    {
        HeapSort ob = new HeapSort();
        int nums[] = {7, -5, 3, 2, 1, 0, 45};
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(nums));
        ob.HeapSort(nums);
        System.out.println("Sorted Array");
        System.out.println(Arrays.toString(nums));
    }
}

Пример вывода:

 Оригинальный массив:
[7, -5, 3, 2, 1, 0, 45]
Сортированный массив
[-5, 0, 1, 2, 3, 45, 7]

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма сортировки слиянием.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел с использованием алгоритма выбора сортировки.