当前位置:   article > 正文

堆排序原理及其实现(C++)_c++堆排序为什么是不稳定的举例说明

c++堆排序为什么是不稳定的举例说明

https://blog.csdn.net/lzuacm/article/details/52853194

堆排序原理及其实现(C++)

1. 堆排序的引入

我们知道简单选择排序的时间复杂度为O(n^2),熟悉各种排序算法的朋友都知道,这个时间复杂度是很大的,所以怎样减小简单选择排序的时间复杂度呢?简单选择排序主要操作是进行关键字的比较,所以怎样减少比较次数就是改进的关键。简单选择排序中第i趟需要进行n-i次比较,如果我们用到前面已排好的序列a[1...i-1]是否可以减少比较次数呢?答案是可以的。举个例子来说吧,A、B、C进行比赛,B战胜了A,C战胜了B,那么显然C可以战胜A,C和A就不用比了。正是基于这种思想,有人提出了树形选择排序:对n个记录进行两两比较,然后在([n/2]向上取整)个较小者之间在进行两两比较,如此重复,直到选出最小记录。但是这种排序算法需要的辅助空间比较多,所以威洛姆斯(J . Willioms)在1964年提出了另一种选择排序,这就是下面要谈的堆排序

2. 什么是堆

首先堆heap是一种数据结构,是一棵完全二叉树且满足性质:所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值.

3. 堆排序思想

堆排序的基本思想是利用heap这种数据结构(可看成一个完全二叉树),使在排序中比较的次数明显减少。

堆排序的时间复杂度为O(n*log(n)), 非稳定排序,原地排序(空间复杂度O(1))。

堆排序的关键在于建堆和调整堆,下面简单介绍一下建堆的过程:

第1趟将索引0至n-1处的全部数据建大顶(或小顶)堆,就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的最后一个节点交换,就使的这组数据中最大(最小)值排在了最后。

第2趟将索引0至n-2处的全部数据建大顶(或小顶)堆,就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第二个节点交换,就使的这组数据中最大(最小)值排在了倒数第2位。

第k趟将索引0至n-k处的全部数据建大顶(或小顶)堆,就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第k个节点交换,就使的这组数据中最大(最小)值排在了倒数第k位。

其实整个堆排序过程中, 我们只需重复做两件事:

  • 建堆(初始化+调整堆, 时间复杂度为O(n));

  • 拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(n*log n) ).

因而堆排序整体的时间复杂度为O(n*log n).

下面通过一组数据说明堆排序的方法:

9, 79, 46, 30, 58, 49

1: 先将待排序的数视作完全二叉树(按层次遍历顺序进行编号, 从0开始),如下图:

img

2:完全二叉树的最后一个非叶子节点,也就是最后一个节点的父节点。最后一个节点的索引为数组长度len-1,那么最后一个非叶子节点的索引应该是为(len-1)/2.也就是从索引为2的节点开始,如果其子节点的值大于其本身的值。则把他和较大子节点进行交换,即将索引2处节点和索引5处元素交换。交换后的结果如图:

img

建堆从最后一个非叶子节点开始即可

3:向前处理前一个节点,也就是处理索引为1的节点,此时79>30,79>58,因此无需交换。

4:向前处理前一个节点,也就是处理索引为0的节点,此时9 < 79,9 < 49, 因此需交换。应该拿索引为0的节点与索引为1的节点交换,因为79>49. 如图:

img

5:如果某个节点和它的某个子节点交换后,该子节点又有子节点,系统还需要再次对该子节点进行判断。如上图因为1处,3处,4处中,1处的值大于3,4出的值,所以还需交换。

img

牢记: 将每次堆排序得到的最大元素与当前规模的数组最后一个元素交换。

伪代码如下:

1、由于是完全二叉树, 故有:

  1. PARENT(i)
  2. return i / 2
  3. LEFT(i)
  4. return 2 * i
  5. RIGHT(i)
  6. 2 * i + 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

2、Heapify 
以最大堆为例,伪代码:

MAX-HEAPIFY(A, i)

  1. l = LIFT(i)
  2. r = RIGHT(i)
  3. if l <= A.heapsize and A[l] > A[i]
  4. largest = l
  5. else largest = i
  6. if r <= A.heapsize and A[r] > A[largest]
  7. largest = r
  8. if largest != i
  9. exchage A[i] with A[largest]
  10. MAX-HEAPIFY(A, largest)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

3、Build Heap 
以最大堆为例,伪代码:

BUILD-MAX-HEAP(A)

  1. A.heap-size = A.length
  2. for A.length / 2 downto 1
  3. MAX-HEAPIFY(A, i)
  • 1
  • 2
  • 3
  • 4

4、Heapsort 
以最大堆为例,伪代码:

HEAPSORT(A) 
BUILD-MAX-HEAP(A)

  1. for i = A.length downto 2
  2. exchange A[1] with A[i]
  3. A.heap-size = A.heap-size - 1
  4. MAX-HEAPIFY(A, 1)
  • 1
  • 2
  • 3
  • 4
  • 5

C++完整代码:

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. void adjust(int arr[], int len, int index)
  7. {
  8. int left = 2*index + 1;
  9. int right = 2*index + 2;
  10. int maxIdx = index;
  11. if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
  12. if(right<len && arr[right] > arr[maxIdx]) maxIdx = right; // maxIdx是3个数中最大数的下标
  13. if(maxIdx != index) // 如果maxIdx的值有更新
  14. {
  15. swap(arr[maxIdx], arr[index]);
  16. adjust(arr, len, maxIdx); // 递归调整其他不满足堆性质的部分
  17. }
  18. }
  19. void heapSort(int arr[], int size)
  20. {
  21. for(int i=size/2 - 1; i >= 0; i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
  22. {
  23. adjust(arr, size, i);
  24. }
  25. for(int i = size - 1; i >= 1; i--)
  26. {
  27. swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
  28. adjust(arr, i, 0); // 将未完成排序的部分继续进行堆排序
  29. }
  30. }
  31. int main()
  32. {
  33. int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
  34. heapSort(array, 8);
  35. for(auto it: array)
  36. {
  37. cout<<it<<endl;
  38. }
  39. return 0;
  40. }
  • 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

为何堆排序是不稳定排序?

当数组中有相等元素时,堆排序算法对这些元素的处理方法不止一种,故是不稳定的。

可重载比较函数的写法:

  1. #include<memory.h>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. void swap(void* x, void* y, size_t sz) {
  5. void* t = malloc(sz);
  6. memcpy(t, x, sz);
  7. memcpy(x, y, sz);
  8. memcpy(y, t, sz);
  9. free(t);
  10. }
  11. void makeHeap(void* x, int i, int n, size_t sz, int(*cmp)(const void*, const void*)) {
  12. char* y = (char*)x;
  13. int l = 2 * i + 1;
  14. int r = 2 * i + 2;
  15. int m;
  16. if (l<n && (*cmp)(y + l*sz, y + i*sz)>0) m = l;
  17. else m = i;
  18. if (r<n && (*cmp)(y + r*sz, y + m*sz)>0) m = r;
  19. if (m != i){
  20. swap(y + i*sz, y + m*sz, sz);
  21. makeHeap(x, m, n, sz, cmp);
  22. }
  23. }
  24. void buildHeap(void* x, int n, size_t sz, int(*cmp)(const void*, const void*)) {
  25. for (int i = n / 2 - 1; i >= 0; i--) makeHeap(x, i, n, sz, cmp);
  26. }
  27. void heapSort(void* x, int n, size_t sz, int(*cmp)(const void*, const void*)) {
  28. buildHeap(x, n, sz, cmp);
  29. char* y = (char*)x;
  30. for (int i = n - 1; i >= 1; i--){
  31. swap(y, y + i*sz, sz);
  32. makeHeap(x, 0, --n, sz, cmp);
  33. }
  34. }
  35. void p(int* x,int n){
  36. for (int k = 0; k < n; k++){
  37. printf("%d ", x[k]);
  38. }
  39. printf("\n");
  40. }
  41. int less(const void* a, const void* b){
  42. return *((int*)a) < *((int*)b);
  43. }
  44. int greater(const void* a, const void* b){
  45. return *((int*)a) > *((int*)b);
  46. }
  47. int main(){
  48. int x[] = { 2, 3, 4, 6, 8, 2, 9, 0 };
  49. // 降序全排列
  50. heapSort(x, 8, sizeof(int), less);
  51. p(x, 8);
  52. // 升序全排列
  53. heapSort(x, 8, sizeof(int), greater);
  54. p(x, 8);
  55. // 最大的4个元素,在数组末尾
  56. heapSort(x, 4, sizeof(int), less);
  57. p(x, 8);
  58. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/707559
推荐阅读
相关标签
  

闽ICP备14008679号