Сортировка кучей(Heap Sort) (реализация на языке Java)

Java   13 марта 2012  Автор статьи:  

Ниже приведен код сортировки кучей на java с комментариями. Также эту сортировку называют пирамидальной

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n]; //В качестве примера берем обычный
for (int i = 0; i < n; i++) { //целочисленный массив, но тут может array[i] = scanner.nextInt(); //быть массив(или коллекция) из } // других типов данных, для которых // задан свой компоратор HeapUtils.sort(array); //Вызов соритровки System.out.println(Arrays.toString(array)); } } class HeapUtils { public static void heapify(int[] array, int size, int pos) { while (2 * pos + 1 < size) { //Процедура нормализации int t = 2 * pos + 1; //подкучи в куче с //головой в pos if (2 * pos + 2 < size && array[2 * pos + 1] < array[2 * pos + 2]) { t = 2 * pos + 2; } if (array[pos] < array[t]) { swap(array, pos, t); pos = t; } else { break; } } } public static int[] heapMake(int[] array) { //Построение кучи из массива при int n = array.length; //помощи функции heapify for (int i = n - 1; i >= 0; i--) {
heapify(array, n, i);
}
return array;
}

public static void sort(int[] array) { //Собственно сама сортировка
int n = array.length;
heapMake(array);
while (n > 0) {
swap(array, 0, n - 1);
n--;
heapify(array, n, 0);
}

}

private static void swap(int[] array, int i, int j) { //Меняет местами
int temp = array[i]; //элементы с
array[i] = array[j]; //индексами i и j
array[j] = temp; //в массиве array
}

}


  • Nikname

    код понятен,но можно написать покороче?!

    • Если и можно, то не на много, и скорее всего это будет одна простыня кода, а главное зачем?

      • Vasilii

        почему то минимальный элемент превращается в ноль. В чем ошибка? подскажите
        import java.util.Arrays;
        public class SortPiramida {
        public static void main(String[] args) {
        int[] arr = {5,4,2,3};
        HeapUtils.sort(arr);
        System.out.println(Arrays.toString(arr));
        }
        }
        class HeapUtils {
        public static void heapify(int[] array, int size, int pos) {
        while (2 * pos + 1 < size) {
        int t = 2 * pos + 1;
        if (2 * pos + 2 < size && array[2 * pos + 1] < array[2 * pos + 2]) {
        t = 2 * pos + 2;
        }
        if (array[pos] = 0; i—) {
        heapify(array, n, i);
        }
        return array;
        }
        public static void sort(int[] array) {
        int n = array.length;
        heapMake(array);
        while (n > 0) {
        obmen(array, 0, n — 1);
        n—;
        heapify(array, n, 0);
        }

        }

        private static void obmen(int[] array, int i, int j) {
        array [i] ^= array[j];
        array [j] ^= array[i];
        array [i] ^= array[j];
        }

Научиться программировать

  • на Delphi

  • на Java

  • на C++