Chinaunix首页 | 论坛 | 博客

分类: C/C++

2018-04-14 20:13:29

不多说了,又把排序搞忘掉了,捡起捡起~
今天我说的堆排序中的堆,跟我们程序运行时,内存分布中的堆(如下图),不一样(此处应该有背景音乐)


今天要讲的堆排序,是以数组方式存储,以二叉树形式视之的一种排序算法~假设,我们有一个数组,要求对其非递减排序,我们可以将整个数组视为一个二叉树(为了方便起见,我们从下标1开始),保证以下性质成立:
(1)在保证下标不越界的情况下,一个元素(下标为idx)的左孩子为2*idx, 右孩子为2*idx+1
(2)保证非叶子节点必须大于其孩子;
我们用如下的代码来保证这条性质(也就是堆排序中的重中之重),heapsz为一个全局变量(为了简便):


点击(此处)折叠或打开

  1. void heapify(int idx, int *arr){
  2.     int maxIdx = idx, lchld = 2*idx, rchld = 2*idx+1, tmp;
  3.     if(lchld<=heapsz&&arr[maxIdx]<arr[lchld]){
  4.         maxIdx = lchld;
  5.     }
  6.     if(rchld<=heapsz&&arr[maxIdx]<arr[rchld]){
  7.         maxIdx = rchld;
  8.     }
  9.     if(maxIdx!=idx){
  10.         tmp = arr[idx];arr[idx]=arr[maxIdx];arr[maxIdx] =tmp;
  11.         heapify(maxIdx, arr);
  12.     }
  13. }

性质保证完了,接下来我们就要建堆了,只需从下标为heapsz/2的下标递减遍历到下标1 即可:


点击(此处)折叠或打开

  1. void create_heap(int *arr){
  2.     for(int i = heapsz/2; i >=1; i--){
  3.         heapify(i, arr);
  4.     }
  5. }

现在我们建成了一个大顶堆,保证每个元素均比其孩子大,将其排序的话,只需将下标为1和下标为heapsz的元素交换,heapsz减1,heapiy(1, arr)即可~~


点击(此处)折叠或打开

  1. void heap_sort(int *arr){
  2.     int tmp;
  3.     for(;heapsz>1;){
  4.         tmp = arr[heapsz];arr[heapsz]=arr[1];arr[1] =tmp;
  5.         heapsz --;
  6.         heapify(1, arr);
  7.     }
  8. }

自己写的一个小程序如下:


点击(此处)折叠或打开

  1. #include <iostream>

  2. using namespace std;
  3. void heapify(int idx, int *arr);
  4. void create_heap(int *arr);
  5. void heap_sort(int *arr);
  6. int heapsz = 10;
  7. int main()
  8. {
  9.     int arr[] = {-1, 87, 76, 34, 3, 22, 57, 90, 19, 65, 12};
  10.     create_heap(arr);
  11.     for(int i = 1; i <= 10; i++)
  12.         cout << arr[i]<<" ";
  13.     cout<<endl;
  14.     heap_sort(arr);
  15.     for(int i = 1; i <= 10; i++)
  16.         cout << arr[i]<<" ";
  17.     cout<<endl;
  18.     return 0;
  19. }
  20. void heapify(int idx, int *arr){
  21.     int maxIdx = idx, lchld = 2*idx, rchld = 2*idx+1, tmp;
  22.     if(lchld<=heapsz&&arr[maxIdx]<arr[lchld]){
  23.         maxIdx = lchld;
  24.     }
  25.     if(rchld<=heapsz&&arr[maxIdx]<arr[rchld]){
  26.         maxIdx = rchld;
  27.     }
  28.     if(maxIdx!=idx){
  29.         tmp = arr[idx];arr[idx]=arr[maxIdx];arr[maxIdx] =tmp;
  30.         heapify(maxIdx, arr);
  31.     }
  32. }
  33. void create_heap(int *arr){
  34.     for(int i = heapsz/2; i >=1; i--){
  35.         heapify(i, arr);
  36.     }
  37. }
  38. void heap_sort(int *arr){
  39.     int tmp;
  40.     for(;heapsz>1;){
  41.         tmp = arr[heapsz];arr[heapsz]=arr[1];arr[1] =tmp;
  42.         heapsz --;
  43.         heapify(1, arr);
  44.     }
  45. }

输出结果如图:


大家轻拍了哈~~~

阅读(40) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册