Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.
前言 堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆排序 堆排序基本介绍
1)堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序;
2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系;
3)每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
堆排序的基本思想是:
1)将待排序序列构造成一个大顶堆;
2)此时,整个序列的最大值就是堆顶的根节点;
3)将其与末尾元素进行交换,此时末尾就为最大值;
4)然后将剩余n-1个元素重新构造成一个堆,这样会得到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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 public class HeapSort { public static void main (String[] args) { int [] arr = new int [8000000 ]; for (int i = 0 ; i < 8000000 ; i++) { arr[i] = (int ) (Math.random() * 8000000 ); } long start = System.currentTimeMillis(); heapSort(arr); long end = System.currentTimeMillis(); System.out.println("8000000个数字排序所用时间:" + (end - start)); } public static void heapSort (int arr[]) { int temp = 0 ; System.out.println("堆排序!!" ); for (int i = arr.length / 2 - 1 ; i >= 0 ; i--) { adjustHeap(arr, i, arr.length); } for (int j = arr.length - 1 ; j > 0 ; j--) { temp = arr[j]; arr[j] = arr[0 ]; arr[0 ] = temp; adjustHeap(arr, 0 , j); } } public static void adjustHeap (int arr[], int i, int lenght) { int temp = arr[i]; for (int k = i * 2 + 1 ; k < lenght; k = k * 2 + 1 ) { if (k + 1 < lenght && arr[k] < arr[k + 1 ]) { k++; } if (arr[k] > temp) { arr[i] = arr[k]; i = k; } else { break ; } } arr[i] = temp; } }
延伸 堆排序 堆排序 HeapSort Heap Sort Algorithm 韩顺平数据结构和算法 堆排序算法(图解详细流程) 五分钟弄懂有点难度的排序:堆排序
<
Data Structure Huffman Tree
Data Structure Binary Tree
>