堆排序

2012-12-28 21:56:21   最后更新: 2015-08-06 17:22:10   访问数量:495




二叉堆数据结构是一种数组对象,是一棵特殊的完全二叉树,分为大根堆和小根堆

对于小根堆,任何一个子树的根节点都小于其左右子树,大根堆则相反

在堆排序算法中,我们使用大根堆,而小根堆通常用于构造优先级队列

 

/* * file: main.c * author: 龙泉居士 * date: 2012-12-28 21:55 */ #include <stdio.h> #include "function/function.h" int heap_sort (int *array, int n) { if (array == NULL || n<=0) { printf ("build_heap param error"); return -1; } else if (n == 1) return 0; build_heap (array, n); int i; for (i=n-1; i>0; --i) { exch (array, 0, i); con_heap (array, 0, i); } return 0; } int main () { int i, n=0; int array[256]; printf ("Please input numbers, end by 9999:\n"); while (1) { scanf ("%d", &array[n]); if (array[n] == 9999) break; ++n; } if (heap_sort(array, n)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

/* * file: function.h * author: 龙泉居士 * date: 2012-12-28 21:56 */ #ifndef FUNCTION_H_20121228 #define FUNCTION_H_20121228 int heap_sort (int *array, int n); int con_heap (int *array, int pos, int n); int build_heap (int *array, int n); int exch (int *array, int a, int b); #endif

 

/* * file: function.c * author: 龙泉居士 * date: 2012-12-28 21:56 */ #include <stdio.h> #include "function.h" int con_heap (int *array, int pos, int n) { if (array == NULL || n<=0) { printf ("con_heap param error"); return -1; } else if (n == 1) return 0; int i=pos; while (i<=n/2-1) { int tmp; if (i*2+2 < n) tmp = array[i*2+1]>array[i*2+2] ? i*2+1 : i*2+2; else tmp = i*2+1; if (array[i]>=array[tmp] || i*2+1 >= n) break; exch(array, i, tmp); i = tmp; } return 0; } int build_heap (int *array, int n) { if (array == NULL || n<=0) { printf ("build_heap param error"); return -1; } else if (n == 1) return 0; int i; for (i=n/2-1; i>=0; --i) if (con_heap (array, i, n)) return -1; return 0; } int exch (int *array, int a, int b) { if (array == NULL) { printf ("build_heap param error"); return -1; } array[a] = array[a]^array[b]; array[b] = array[a]^array[b]; array[a] = array[a]^array[b]; return 0; }

 

 

这个排序算法的时间复杂度是O(nlogn),空间复杂度是O(1),是一个比较理想的排序算法,常用在操作系统的进程调度算法中(优先级队列的调度算法)

这是一个典型的基于数据结构发明的算法

 

为什么要使用大根堆而不是小根堆呢?事实上,小根堆也是可以完成这个任务的,对于n个元素的数组array来说,如果选用小根堆,则第i次循环是排序i到n的自数列,需要传递参数i,而如果使用大根堆,则每次都将最大元素放到最后,只需传递数组个数n即可,子序列即0到n,其实基于大根堆的算法和基于小根堆的算法是大同小异的

 

上面的代码中有一个问题:对于exch函数,如果参数a和b的值是一样的,那么结果两个值都会被清零,这个问题的解决方法就参看我的另一个代码吧:

快速排序

 






读书笔记      技术帖      算法      算法导论            heap      数据结构      龙潭书斋      排序      heapsort      堆排序      交换     


京ICP备15018585号