本文實(shí)例講述了java堆排序原理與實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：
堆是一個(gè)數(shù)組，被看成一個(gè)近似完全二叉樹。
舉例說(shuō)明：
堆的性質(zhì)：
1.已知元素在數(shù)組中的序號(hào)為i
其父節(jié)點(diǎn)的序號(hào)為 i/2的整數(shù)
其左孩子節(jié)點(diǎn)的序號(hào)為2*i
其右孩子節(jié)點(diǎn)的序號(hào)為2*i+1
2.堆分為最大堆和最小堆
在最大堆中，要保證父節(jié)點(diǎn)的值大于等于其孩子節(jié)點(diǎn)的值
在最小堆中，要保證父節(jié)點(diǎn)的值小于等于其孩子節(jié)點(diǎn)的值
java實(shí)現(xiàn)堆排序
|
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
|
public class myheapsort { public void heap_sort(int[] a) { /** * 這個(gè)函數(shù)完成堆排序 * 先構(gòu)建一個(gè)最大堆 * 將數(shù)組中第一個(gè)元素和最后一個(gè)交換， * 堆的長(zhǎng)度減一 * 在從第一個(gè)位置開始保證堆的性質(zhì)調(diào)用max_heapify()函數(shù)。 * 這樣保證目前最大的元素在數(shù)組的最后位置。 * 以此類推，直到最后一個(gè)元素。 */ build_max_heap(a); for (int i = a.length - 1; i >= 1; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; max_heapify(a, 0, i); } } public void build_max_heap(int[] a) { /** * 這個(gè)函數(shù)用來(lái)構(gòu)建堆 * a:待排序的數(shù)組 * （for循環(huán)中i的值從數(shù)組長(zhǎng)度的一般開始取，是因?yàn)橥耆鏄涞男再|(zhì)， * 一半的節(jié)點(diǎn)葉根節(jié)點(diǎn)所以從葉節(jié)點(diǎn)開始向上遍歷來(lái)保證堆的性質(zhì)） */ for (int i = a.length/2; i >= 0; i--) { max_heapify(a, i, a.length); } } public void max_heapify(int[] a, int i, int heap_size) { /**這個(gè)函數(shù)用來(lái)維護(hù)堆的性質(zhì)， * 保證以序號(hào)為i的元素為根節(jié)點(diǎn)的子樹中，父節(jié)點(diǎn)的值大于其孩子節(jié)點(diǎn)的值。 * a:待排序數(shù)組 * i：在數(shù)組a中的序號(hào) * heap_size:堆的大小 */ int largest = i; int l = i * 2 + 1; int r = i * 2 + 2; if (l < heap_size && a[l] > a[i]) largest = l; if (r < heap_size && a[r] > a[largest]) largest = r; if (largest != i) { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; max_heapify(a, largest, heap_size); } } public static void main(string[] args) throws exception { system.out.println("服務(wù)器之家測(cè)試結(jié)果："); int[] a = new int[]{1,3,2,5,34,23,44,15,67,45}; new myheapsort().heap_sort(a); for (int x : a) system.out.println(x); }} |
代碼中例子的運(yùn)行結(jié)果：
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
原文鏈接：https://blog.csdn.net/u014028027/article/details/78626416
