排序算法之堆排序
1. 堆排序
1.1 堆排序基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为
O(nlogn)
,它也是不稳定排序。
- 堆是具有以下性质的完全二叉树:
- 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
- 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
- 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
大顶堆
小顶堆
一般升序采用大顶堆,降序采用小顶
1.2 堆排序基本思想
- 将待排序序列构造成一个大顶堆
- 此时,整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换,此时末尾就为最大值。
- 然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。如此反复执行,便能得到一个有序序列了
1.2.1 图解堆排序
给你一个数组 {4,6,8,5,9}
, 要求使用堆排序法,将数组升序排序
。
1.3 堆排序代码实现
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
| public class HeapSort {
public static void main(String[] args) {
}
public static void heapSort(int[] arr) { System.out.println("堆排序"); int temp = 0; 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 length) { int temp = arr[i]; for (int k = i*2 +1; k < length; k = k*2 +1) { if(k+1 <length && arr[k]<arr[k+1]) { k++; } if(arr[k]>temp) { arr[i] = arr[k]; i = k; }else { break; } } arr[i] = temp; } }
|
1.3.1 测试结果及速度
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
| public class HeapSort {
public static void main(String[] args) { int[] arr = new int[80000000]; for (int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random()*800000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String format1 = simpleDateFormat.format(date1); System.out.println("排序前的时间:"+format1); heapSort(arr); Date date2 = new Date(); String format2 = simpleDateFormat.format(date2); System.out.println("排序后的时间:"+format2); } }
|