赞
踩
本文以升序为例,进行堆排序讲解。堆排序是建立在大堆的思想上的,通过将数组排成大堆,然后将堆数组中的头元素与尾元素进行交换,最后对除去尾元素外的全部堆数组元素进行大堆排序,如此循环往复,即可完成升序堆排序。
想要实现堆排序,首先就要建大堆,那为什么就不能小堆呢?那是因为如果建小堆,数组头元素即为最小值,然后需要将后面N-1个元素建小堆,这就造成时间复杂度提升到了N^2;所以不能建小堆来排升序。那如何建大堆呢,有两种方法,一种是从下往上建大堆,另一种是从上往下建大堆。我从上往下建大堆开始讲起,从上往下建大堆,需要由尾元素孩子的下标算出该数组的尾元素的父亲的下标,然后再对比孩子和父亲的大小,如果孩子比父亲大,就将孩子和父亲相互替换,之后将父亲的下标值给孩子,再算出新的父亲的下标值,重复以上步骤,直至孩子元素的下标等于0,就完成了大堆的建立。
完成大堆的建立之后,就是堆排序了,堆排序的思路上面已经讲过,下面是示意图:
- // 建堆
- void AdjustDwon(int* a, int n, int root)
- {
- assert(a);
- int child = root * 2 + 1;
- while (child < n)
- {
- if (a[child + 1] > a[child] && child + 1 < n)//此处的child + 1 < n表示数组最后一个数不加入建小堆中
- {
- child = child + 1;
- }
- if (a[child] > a[root])
- {
- swap(&a[child], &a[root]);
- root = child;
- child = child * 2 + 1;
- }
- else
- {
- break;
- }
- }
- }
- //堆排序
- void HeapSort(int* a, int n)
- {
- assert(a);
- for (int i = n / 2 - 1; i >= 0; i--)
- {
- AdjustDwon(a, n, i);
- }
- int end = n - 1;
- while (end > 0)
- {
- swap(&a[0],&a[end]);
- AdjustDwon(a, end, 0);
- end--;
- }
- }
建堆需要的时间复杂度为O(N),堆排序所需要的时间复杂度为N*log(N),故堆排序的时间复杂度约等于N*log(N)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。