|
堆的定义:
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素. 堆排序算法的过程如下:1)得到当前序列的最小(大)的元素 2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面 3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.重复上面的过程,直到序列调整完毕为止.
before Heap sort: 71 18 151 138 160 63 174 169 79 78 // 开始调整前半段数组元素 71 18 151 138 160 63 174 169 79 78 71 18 151 169 160 63 174 138 79 78 71 18 174 169 160 63 151 138 79 78 71 169 174 138 160 63 151 18 79 78 174 169 151 138 160 63 71 18 79 78 // 开始进行全局的调整 169 160 151 138 78 63 71 18 79 174 160 138 151 79 78 63 71 18 169 174 151 138 71 79 78 63 18 160 169 174 138 79 71 18 78 63 151 160 169 174 79 78 71 18 63 138 151 160 169 174 78 63 71 18 79 138 151 160 169 174 71 63 18 78 79 138 151 160 169 174 63 18 71 78 79 138 151 160 169 174 18 63 71 78 79 138 151 160 169 174 //*****************************************
/*
Name: 堆排序算法 Author: zhuqing
Des cription: 堆排序算法的过程演示 Date: 18-08-03 09:50 Copyright: */ #include<stdio.h>
#define N 6 int k,j; /* 建堆函数 */ void build(int *a,int i,int n){ int tmp; k=i; j=2*k+1; while(j<=n){ if(j<n && a[j]<a[j+1]) j++; if(a[k]>=a[j])break; tmp=a[k]; a[k]=a[j]; a[j]=tmp; k=j; j=2*j+1; } } /* 打印数组函数 */ void prnt(int *a,int n){ int i; printf("\n"); for(i=0;i<n;i++){ printf("%3d",a[i]); } printf("\n"); } /* 打印堆函数 */ void prnthp(int *a,int b1,int b2){ int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum<=size){ sum+=item; h++; item*=2; } item=1; cnt=0; start=b1; tmp=1; printf("\n--------------------------------------------\n"); printf(" 堆：\n"); while(1){ for(i=0;i<h;i++){ for(j=0;j<h-i;j++) printf(" "); for(j=0;j<i+1;j++)printf(" "); for(j=0;j<tmp;j++){ if(cnt>size-1)goto end; printf("%4d",a[cnt++]); } printf("\n"); tmp*=2; } } end: printf("\n"); return; } /* 打印已排序数组函数 */ void prntar(int *a,int b2,int len){ int i; printf(" 已排序：\n"); for(i=0;i<b2;i++){ printf(" "); } for(i=b2;i<=len;i++){ printf("%3d",a[i]); } printf("\n"); } main(){ /* int a[]={-1,2,5,1,0,-3,-2,8,6}; */ int a[50]; int i; int tmp; int sum; int num; int len; printf(" 堆排序\n"); printf("\n============================================\n"); printf("\n 请输入待排序数组个数,以回车结束：\n"); scanf("%3d",&len); printf("\n 请输入待排序数组,以回车结束：\n"); for(i=0;i<len;i++) scanf("%3d",&a[i]); tmp=1;sum=0; while(sum+tmp<=len){ sum+=tmp; tmp*=2; } printf("\n============================================\n"); printf("\n 初始数组： \n"); prnt(a,len); /* 建初始堆 */ for(i=sum-1;i>=0;i--) build(a,i,len-1); prnthp(a,0,len-1); /* 改建堆 */ for(i=0;i<len-1;i++){ tmp=a[0]; a[0]=a[len-1-i]; a[len-1-i]=tmp; build(a,0,len-2-i); prnthp(a,0,len-2-i); prntar(a,len-1-i,len-1); } printf("\n--------------------------------------------\n"); printf("\n 排序结果：\n"); prnt(a,len); printf("\n============================================\n\n"); getch(); } //*****************************************************************
堆排序简介： 堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。 堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。 二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。 堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。 堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。 堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。 二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。 堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。 根据要求实现程序如下： #include <stdio.h> void push_heap(int *array, int pos, int value) { int i; for(i=pos; i/2>0 && array[i/2]>value; i/=2) { array[i] = array[i/2]; } array[i] = value; } void make_heap(int *data, int *array, int len) { for(int i=0; i<len; ++i) { push_heap(array, i+1, data[i]); } } int pop_heap(int *array, int last) { int value = array[1]; array[1] = array[last]; int i=1; while(2*i < last) { int min = array[2*i] < array[2*i+1] ? array[2*i] : array[2*i+1]; int pos = array[2*i] < array[2*i+1] ? (2*i) : (2*i+1); if(array[i] > min) { int tmp = array[i]; array[i] = min; array[pos] = tmp; i = pos; } } return value; } void sort_heap(int *data, int *array, int len) { for(int i=0; i<len; ++i) { data[i] = pop_heap(array, len-i); } } int main() { int data[] = {12, 34, 23, 3, 1, 45, 87, 99}; int array[10]; make_heap(data, array, 8); for(int i=1; i<=8; ++i) { printf("%d ", array[i]); } printf("\n"); sort_heap(data, array, 8); for(int i=0; i<8; ++i) { printf("%d ", data[i]); } printf("\n"); return 0; }
堆排序的空间复杂度要求O(1)，上面程序使用了辅助数组，所以其空间复杂度为O(n)，不符合要求，所以又写了一个,如下： #include <stdio.h> int swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void adjust(int *array, int i, int n) { int min, pos; while(1) { if((2*i+2) < n) { min = array[2*i+1] < array[2*i+2] ? array[2*i+1] : array[2*i+2]; pos = array[2*i+1] < array[2*i+2] ? (2*i+1) : (2*i+2); if(array[i] < min) { break; } swap(&array[i], &array[pos]); i = pos; } else if((2*i+2) == n) { min = array[2*i+1]; pos = 2*i+1; if(array[i] < min) { break; } swap(&array[i], &array[pos]); i = pos; } else { break; } } } void heap_sort(int *array, int n) { //构建最小堆 for(int j=(n-1)/2; j>=0; --j) { adjust(array, j, n); } //降序排列 for(int i=n; i>1; --i) { swap(&array[0], &array[i-1]); adjust(array, 0, --n); } } int main() { int data[] = {12, 34, 23, 3, 1, 45, 87, 99}; heap_sort(data, 8); for(int i=0; i<8; ++i) { printf("%d ", data[i]); } printf("\n"); return 0; } |
|
|
