概述
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点
算法描述
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区
将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]
由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完
动图演示
算法实现
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
|
public class Test { public static void main(String[] args) { int[] arr = {16, 7, 3, 20, 17, 8}; System.out.println("排序前:"); for (int i : arr) { System.out.print(i + " "); } System.out.println(); heapSort(arr); System.out.println("排序后:"); for (int i : arr) { System.out.print(i + " "); } }
private static void heapSort(int[] arr) { for (int i = (arr.length - 1) / 2; i >= 0; i--) { adjustHeap(arr, i, arr.length); } for (int i = arr.length - 1; i > 0; i--) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, i); } }
private static void adjustHeap(int[] arr, int parent, int length) { int temp = arr[parent]; int lChild = 2 * parent + 1; while (lChild < length) { int rChild = lChild + 1; if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } if (temp >= arr[lChild]) { break; } arr[parent] = arr[lChild]; parent = lChild; lChild = 2 * lChild + 1; } arr[parent] = temp; } }
|
运行结果
PS.
搬运地址: 十大经典排序算法(动图演示) - 一像素 - 博客园 (cnblogs.com)