1 堆排序
堆是一種重要的數(shù)據(jù)結(jié)構(gòu)，分為大根堆和小根堆，是完全二叉樹, 底層如果用數(shù)組存儲(chǔ)數(shù)據(jù)的話，假設(shè)某個(gè)元素為序號(hào)為i(Java數(shù)組從0開始,i為0到n-1),如果它有左子樹，那么左子樹的位置是2i+1，如果有右子樹，右子樹的位置是2i+2，如果有父節(jié)點(diǎn)，父節(jié)點(diǎn)的位置是(n-1)/2取整。最大堆的任意子樹根節(jié)點(diǎn)不小于任意子結(jié)點(diǎn)，最小堆的根節(jié)點(diǎn)不大于任意子結(jié)點(diǎn)。
所謂堆排序就是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)來(lái)對(duì)數(shù)組進(jìn)行排序，在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的性質(zhì)可知，最大的值一定在堆頂。堆排序一種不穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為O(nlogn)。
2 算法思想
（1）構(gòu)建最大堆；
（2）選擇頂，并與第0位置元素交換；
（3）由于步驟（2）的的交換可能破環(huán)了最大堆的性質(zhì)，即第0位置的元素不再是最大元素，則需要調(diào)用maxHeap調(diào)整堆(沉降法)，根據(jù)實(shí)際情況重復(fù)步驟（2）。
堆排序中最重要的算法就是maxHeap，該函數(shù)假設(shè)一個(gè)元素的兩個(gè)子節(jié)點(diǎn)都滿足最大堆的性質(zhì)(即左、右子樹都是最大堆)，只有根元素可能違反最大堆性質(zhì)，那么把該元素以及左右子節(jié)點(diǎn)的最大元素找出來(lái)，如果該元素已經(jīng)最大，那么整棵樹都是最大堆，程序退出，否則交換根元素與最大元素的位置，繼續(xù)調(diào)用maxHeap構(gòu)建最大元素所在的子樹。
3 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
|
public static void main(String[] args) { int[] arr = {3, 2, 1, 0, -1, -2, -3}; System.out.println("Before heap:"); printArray(arr); heapSort(arr); System.out.println("After heap sort:"); printArray(arr); } public static void heapSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } buildMaxHeap(arr); //構(gòu)建最大堆 for (int i = arr.length - 1; i >= 1; i--) { exchangeElements(arr, 0, i); //交換堆頂和第0位置元素 maxHeap(arr, i, 0); //因?yàn)榻粨Q元素后，有可能違反堆的性質(zhì)，所以沉降元素 } } private static void buildMaxHeap(int[] arr) { //構(gòu)建最大堆 if (arr == null || arr.length <= 1) { return; } int half = arr.length / 2; for (int i = half; i >= 0; i--) { maxHeap(arr, arr.length, i); } } private static void maxHeap(int[] arr, int heapSize, int index) { int left = index * 2 + 1; //左子樹上的元素 int right = index * 2 + 2; //右子樹上的元素 int largest = index; //初始化最大元素 if (left < heapSize && arr[left] > arr[index]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (index != largest) { //判斷根元素是否為最大元素 exchangeElements(arr, index, largest); maxHeap(arr, heapSize, largest); } } public static void printArray(int[] arr) { //打印數(shù)組 System.out.print("{"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); if (i < arr.length - 1) { System.out.print(", "); } } System.out.println("}"); } public static void exchangeElements(int[] arr, int index1, int index2) { //交換元素 int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; }} |
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
