本帖最后由 forlinx2013 于 2014-1-24 09:09 编辑
欢迎大家来到飞凌爱板网专区，对嵌入式技术感兴趣的朋友不妨多多关注一下，我们提供了公司所有开发板的所有资料，也会更新大量技术文章，欢迎大家一块学习提高！！！
主机平台：Gentoo Linux with Kernel Linux 3.4.36-gentoo 编译器版本：gcc (Gentoo 4.6.3 p1.9, pie-0.5.2) 4.6.3
堆排序（Heap Sort）堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录. 堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1），
它是不稳定的排序方法。 如果需求是从很大的数据中选取特定的几个最大活最小值，那么堆排序是最好的选择。 堆排序的基本步骤就是： 1.初始建堆 2.将堆顶元素与有序区的第一个元素交换 3.然后对堆顶元素开始调整堆，跳转到2执行。直到全部有序。
声明：下面算法的实现中，数组的存储位于data[1]-------data[n] 该算法中最核心的算法是堆的调整算法： 1 //堆调整 2 //data[],要排序的数组 3 //target,要调整的元素位置 4 //n,数组大小 5 void AdjustHeap(int data[],int target,int n) 6 { 7 int nChild; 8 int nTemp; 9 10 nTemp = data[target];//暂存 11 while(target * 2 <= n) 12 { 13 nChild = target * 2;//nChild指向左孩子 14 if(nChild + 1 <= n && data[nChild] < data[nChild + 1]) 15 { 16 nChild++;//nChild指向关键字大的孩子（看是否有左孩子，若有，则左右孩子比较） 17 } 18 if(nTemp < data[nChild])//孩子节点比父节点大，则进行孩子节点移到父节点的位置 19 { 20 data[target] = data[nChild]; 21 target = nChild;//再处理刚刚调整过的节点的字节点 22 } 23 else break; 24 } 25 data[target] = nTemp;//最后将要调整的元素放到合适的位置 26 } //堆调整 //data[],要排序的数组 //target,要调整的元素位置 //n,数组大小 void AdjustHeap(int data[],int target,int n) { int nChild; int nTemp;
nTemp = data[target];//暂存 while(target * 2 <= n) { nChild = target * 2;//nChild指向左孩子 if(nChild + 1 <= n && data[nChild] < data[nChild + 1]) { nChild++;//nChild指向关键字大的孩子（看是否有左孩子，若有，则左右孩子比较） } if(nTemp < data[nChild])//孩子节点比父节点大，则进行孩子节点移到父节点的位置 { data[target] = data[nChild]; target = nChild;//再处理刚刚调整过的节点的字节点 } else break; } data[target] = nTemp;//最后将要调整的元素放到合适的位置 }
整体实现代码：
27 /**************** 28 * 堆排序算法 29 * 排序数组下标从1开始 30 */ 31 #include <stdio.h> 32 33 enum{MAX = 1000+1,}; 34 35 int data[MAX]; 36 static inline swap(int x,int y) 37 {/* 38 x ^= y; 39 y ^= x; 40 x ^= y; 41 */ 42 int tmp; 43 tmp = data[x]; 44 data[x] = data[y]; 45 data[y] = tmp; 46 } 47 //堆调整 48 //data[],要排序的数组 49 //target,要调整的元素位置 50 //n,数组大小 51 void AdjustHeap(int data[],int target,int n) 52 { 53 int nChild; 54 int nTemp; 55 56 nTemp = data[target];//暂存 57 while(target * 2 <= n) 58 { 59 nChild = target * 2; 60 if(nChild + 1 <= n && data[nChild] < data[nChild + 1]) 61 { 62 nChild++;//nChild指向关键字大的孩子 63 } 64 if(nTemp < data[nChild]) 65 { 66 data[target] = data[nChild]; 67 target = nChild;//再处理刚刚调整过的节点的字节点 68 } 69 else break; 70 } 71 data[target] = nTemp;//最后将要调整的元素放到合适的位置 72 } 73 74 //堆排序算法 75 //data，要排序的数组 76 //n，数组大小 77 void HeapSort(int data[],int n) 78 { 79 int i; 80 //初始建堆 81 for(i = n/2;i > 0;--i) 82 { 83 AdjustHeap(data,i,n); 84 } 85 //每次循环将堆顶元素与有序区第一个元素交换，然后再调整堆 86 for(i = n;i > 1;--i) 87 { 88 swap(1,i); 89 AdjustHeap(data,1,i - 1); 90 } 91 } 92 93 int main() 94 { 95 freopen("random","r",stdin); 96 freopen("oder","w",stdout); 97 int i; 98 for(i = 1;i <= MAX;++i) 99 { 100 scanf("%d",&data); 101 } 102 //stderr("开始排序\n"); 103 HeapSort(data,MAX); 104 //stderr("排序结束\n"); 105 for(i = 1;i <= MAX;++i) 106 { 107 printf("%d\n",data); 108 } 109 return 0; 110 } 原创作品，转载请标明出处 | 
发表于 2014-1-24 08:43:48
楼主
/3 
