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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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

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

    • http://cybern.ru/ lordrp

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

      • 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++