算法-java代码实现堆排序

时间:2022-01-29 06:24:21

堆排序

第7节 堆排序练习题

对于一个int数组,请编写一个堆排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例:
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
 
Java (javac 1.7)

代码自动补全

 
 
 
 
 
1
import java.util.*;
2

3
public class HeapSort {
4
    public int[] heapSort(int[] A, int n) {
5
        int lastIndex = n - 1;
6
        buildMaxHeap(A, lastIndex);//建立最大堆
7
        while(lastIndex > 0){
8
            swap(A, 0, lastIndex);
9
            if(--lastIndex == 0)//只剩一个元素,就不用调整堆了,排序结束
10
                break;
11
            adjustHeap(A,0,lastIndex);    
12
        }
13
        return A;
14
    }
15

16
    public void buildMaxHeap(int[] arr, int lastIndex) {
17
        // 从最后一个元素的父节点开始进行调整,一直调整到根节点结束
18
        int j = (lastIndex - 1) / 2;
19
        while (j >= 0) {
20
            int rootIndex = j;
21
            adjustHeap(arr, rootIndex, lastIndex);
22
            j--;
23
        }
24
    }
25

26
    public void adjustHeap(int[] arr, int rootIndex, int lastIndex) {//从根节点开始往下调整
27
        int biggerIndex = rootIndex;
28
        int leftChildIndex = rootIndex * 2 + 1; 
29
        int rightChildIndex = rootIndex * 2 + 2;
30

31
        if(rightChildIndex <= lastIndex){//如果右孩子存在,则左孩子一定存在
32
            if(arr[rightChildIndex] > arr[rootIndex] || arr[leftChildIndex] > arr[rootIndex]){
33
                //将子节点更大的元素下标赋值给biggerIndex
34
                biggerIndex = arr[rightChildIndex] > arr[leftChildIndex]?rightChildIndex:leftChildIndex;
35
            }
36
        }
37
        else if(leftChildIndex <= lastIndex){//保证左孩子存在,且不能越界
38
            if(arr[leftChildIndex] > arr[rootIndex]){
39
                biggerIndex = leftChildIndex;
40
            }
41
        }
42
        if(biggerIndex != rootIndex){
43
            swap(arr, biggerIndex, rootIndex);
44
            adjustHeap(arr, biggerIndex, lastIndex);
45
        }
46

47
    }
48

49
    public void swap(int[] arr, int biggerIndex, int rootIndex) {
50
        int temp = arr[rootIndex];
51
        arr[rootIndex] = arr[biggerIndex];
52
        arr[biggerIndex] = temp;
53
    }
54
}
 
 
您的代码已保存
答案正确:恭喜!您提交的程序通过了所有的测试用例