【Java】数据结构-堆排序（完整代码）

| | | | 1.7k

堆排序和其他排序算法时间复杂度比较截图

image-20210630150821902

堆排序执行（完整代码）

MaxHeap.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data  = new Array<>();
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值，表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int  parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素右孩子节点的索引
    private int rightchild(int index){
        return index * 2 + 2;
    }

    // 向堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()- 1);
    }

    private void siftUp(int k){

        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
            data.swap(k , parent(k));
            k = parent(k);
        }
    }

    // 看堆中的最大元素
    public E findMax(){
        if(data.getSize()==0)
            throw new IllegalArgumentException("can not findMax when heap is empty!");
        return data.get(0);
    }

    // 取出堆中最大元素
    public E extractMax(){

        E ret = findMax();

        data.swap(0, data.getSize()-1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    private void siftDown(int k ){

        while(leftChild(k) < data.getSize() ){

            int j = leftChild(k);
            if(j + 1 < data.getSize() && data.get(j+1).compareTo(data.get(j))>0){
                j = rightchild(k);
            }
            //data[j] 是左右孩子中最大值

            if(data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k,j);
            k = j;
        }
    }
}

Array.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
public class Array<E> {

    private E[] data;
    private int size;  //大小

    // 构造函数 转入数组的容量capacity构造Array
    public Array(int capacity){
        data =(E[])new Object[capacity];
        size = 0    ;
    }

    // 无参的构造函数，默认数组的容量capacity = 10
    public Array(){
        this(10); //调用有参构造函数传入10设定初始大小
    }

    // 获取数组中元素个数
    public int getSize(){
        return size;
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){

//         if(size == data.length) {
//             throw new IllegalArgumentException("AddLast failed. Array is full.");
//         }
//         data[size] = e;
//         size ++;
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

    // 在第index个位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size ){
            throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
        }

        if(size == data.length) {
            resize(2 * data.length);
        }

        for(int i = size - 1 ; i >= index ; i  --){
            data[i + 1]=data[i];
        }
        data[index] = e;
        size ++;
    }

    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("set failed. Index is illegal.");
        data[index] = e;

    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i++)
        {
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i++)
        {
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
        {
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        }
        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
        {
            data[i-1] = data[i];
        }
        size --;
        data[size] = null; //让他自动回收 非必须写  loitering objects ！= memory leak

        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }

    // 从数组中删除第一个元素，返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素，返回删除的元素
    public E removeLast(){
        return remove(size-1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    public void swap(int i , int j){

        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //system.out.print()所输出的类型toString覆盖
    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d \n", size, data.length));
        res.append('[');
        for(int i = 0 ; i < size ; i ++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }
}

SortingHelper.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
public class SortingHelper {

    private SortingHelper(){} //私有类

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){

        for(int i = 1; i< arr.length; i++)
            if (arr[i - 1].compareTo(arr[i]) > 0)
            return false;
        return true;
    }

    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
        long startTime = System.nanoTime();
        if(sortname.equals("SelectionSort")) {
            SelectionSort.sort(arr);
        } else if(sortname.equals("InsertionSort"))
            InsertionSort.sort(arr);
        else if(sortname.equals("InsertionSort2"))
            InsertionSort.sort2(arr);
        else if(sortname.equals("MergeSort"))
            MergeSort.sort(arr);
        else if(sortname.equals("MergeSort2"))
            MergeSort.sort2(arr);
        else if(sortname.equals("MergeSort3"))
            MergeSort.sort3(arr);
        else if(sortname.equals("MergeSort4"))
            MergeSort.sort4(arr);
        else if(sortname.equals("MergeSortBU"))
            MergeSort.sortBU(arr);
        else if(sortname.equals("QuickSort"))
            QuickSort.sort(arr);
        else if(sortname.equals("QuickSort2"))
            QuickSort.sort2ways(arr);
        else if(sortname.equals("QuickSort3"))
            QuickSort.sort3ways(arr);
        else if(sortname.equals("HeapSort"))
            HeapSort.sort(arr);
        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零

        if(!SortingHelper.isSorted(arr))
            throw new RuntimeException(sortname + "failed");
        System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
    }
}

ArrayGenerator.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
import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

       Integer[] arr = new Integer[n];
       for(int i = 0; i < n ; i++)
           arr[i] = i;
       return arr;
    }

    // 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0 ; i < n; i++)
            arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
        return arr;
    }
}

HeapSort.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
import java.util.Arrays;

public class HeapSort {

    private HeapSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){

        MaxHeap<E> maxHeap = new MaxHeap<>();
        for(E e: data)
            maxHeap.add(e);

        for(int i = data.length - 1 ; i >= 0 ; i --)
            data[i] = maxHeap.extractMax();
    }

    public static void main(String[] args) {

        int n = 1000000;

        Integer[] arr = ArrayGenerator.generateRandomArray(n , n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        Integer[] arr4 = Arrays.copyOf(arr, arr.length);
        Integer[] arr5 = Arrays.copyOf(arr, arr.length);

        sort(arr5);

        for(int i = 0 ; i < n ; i ++){
            System.out.println(arr5[i]);
        }

        SortingHelper.sortTest("MergeSort", arr);
        SortingHelper.sortTest("QuickSort2", arr2);
        SortingHelper.sortTest("QuickSort3", arr3);
        SortingHelper.sortTest("HeapSort", arr4);
    }
}

我的个人博客

孤桜懶契：http://gylq.github.io

本文标题:【Java】数据结构-堆排序（完整代码）

文章作者:孤桜懶契

发布时间:2021年06月30日 - 15:07:44

最后更新:2022年05月20日 - 11:47:45

原始链接:https://gylq.gitee.io/posts/49.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
欢迎光临
❤️
孤桜懶契
请多关照
❤️
❤️