FilesExpand file tree

 master

/

HeapSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (62 loc) · 1.87 KB

 master

/

HeapSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (62 loc) · 1.87 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.Arrays;

/**

* @program JavaBooks

* @description: 堆排序

* @author: mf

* @create: 2019/08/14 15:24

*/

/*

- 创建一个堆 H[0……n-1]；

- 创建一个大根堆

- 堆顶和堆尾交换

- 重复第三步骤

*/

public class HeapSort {

public static void main(String[] args) {

int[] arr = {3, 5, 1 , 4, 2};

System.out.println("Heap Sort...");

System.out.println(Arrays.toString(arr));

heapSort(arr);

System.out.println(Arrays.toString(arr));

}

public static void heapSort(int[] arr) {

if (arr == null || arr.length < 2) return;

for (int i = 0; i < arr.length; i++) {

heapInsert(arr, i); // 依次从0～i形成大根堆

}

int heapSize = arr.length;

swap(arr, 0, --heapSize);

while (heapSize > 0) {

heapify(arr, 0, heapSize);

swap(arr, 0, --heapSize);

}

}

public static void heapInsert(int[] arr, int index) {

// 建立大根堆

while (arr[index] > arr[(index - 1) / 2]) {

swap(arr, index, (index - 1) / 2);

index = (index - 1) / 2;

}

}

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public static void heapify(int[] arr, int index, int heapSize) {

// 调整成大根堆

int left = index * 2 + 1;

while (left < heapSize) {

int largest = left + 1 < heapSize && arr[left + 1] > arr[left]

? left + 1

: left;

largest = arr[largest] > arr[index] ? largest : index;

if (largest == index) {

break; // 自己已经是最大了， 直接跳出

}

swap(arr, largest, index);

index = largest;

left = index * 2 + 1;

}

}

}