常用排序算法递归篇之堆排序
在讲堆排序之前，我们先来了解一下什么是堆，堆的定义如下：
n个关键字序列array[0...n-1]称为（Heap），当且仅当该序列满足如下性质：
/***************************************************************************** 函 数 名 : heap_adjust 功能描述 : 堆排序 输入参数 : array 待调整的堆数组 length 数组的长度 输出参数 : 无 返 回 值 : 无 修改历史 : 1.日 期 : 2012/08/23 作 者 : liguangting 修改内容 : *****************************************************************************/void heap_sort(int *array, int length){ int i = 0; if (NULL == array || 0 == length) { return; } //构造大顶堆 for (i = length / 2 - 1; i >= 0; i--) { heap_adjust(array, i, length); } //从最后一个元素开始对数组进行调整，不断缩小调整的范围直到第一个元素 for (i = length - 1; i > 0; i--) { //交换第一个元素和当前的最后一个元素，保证当前的最后一个元素在当前数组中是最大的 swap(array[0], array[i]); //调整完后的第一个元素是当前数组的最大元素 heap_adjust(array, 0, i); }}/***************************************************************************** 函 数 名 : heap_adjust 功能描述 : 根据数组构建大顶堆 输入参数 : array 待调整的堆数组 index 待调整的数组元素的位置 length 数组的长度 输出参数 : 无 返 回 值 : 无 修改历史 : 1.日 期 : 2012/08/23 作 者 : liguangting 修改内容 : *****************************************************************************/void heap_adjust(int *array, int index, int length){ int child; int temp = array[index]; if (2 * index + 1 >= length) { return; } //子结点位置 = 2 * 父结点位置 + 1 child = 2 * index + 1; //得到子结点中较大的结点 if (child < length - 1 && array[child + 1] > array[child]) { ++child; } //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (temp < array[child]) { array[index] = array[child]; } else { return; } //最后把需要调整的元素值放到合适的位置 array[child] = temp; heap_adjust(array, child, length);}
上面的堆调整用了递归的思路，其实也不难看出，我们可以用非递归的方法来完成一轮堆调整，可以参考如下实现：
/***************************************************************************** 函 数 名 : heap_adjust 功能描述 : 根据数组构建大顶堆 输入参数 : array 待调整的堆数组 index 待调整的数组元素的位置 length 数组的长度 输出参数 : 无 返 回 值 : 无 修改历史 : 1.日 期 : 2012/08/23 作 者 : liguangting 修改内容 : *****************************************************************************/void heap_adjust(int *array, int index, int length){ int child; int temp = array[index]; for (; 2 * index + 1 < length; index = child) { //子结点位置 = 2 * 父结点位置 + 1 child = 2 * index + 1; //得到子结点中较大的结点 if (child < length - 1 && array[child + 1] > array[child]) { ++child; } //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (temp < array[child]) { array[index] = array[child]; } else { break; } //最后把需要调整的元素值放到合适的位置 array[child] = temp; }}
堆排序的每一趟排序结果都是选出无序区的最大值或最小值，跟选择排序的思路是一致的。但是在处理过程中却截然不同，那堆排序与选择排序有什么不同点呢？
直接选择排序中，为了从array[0...n-1]中选出关键字最小的记录，必须进行n-1次比较，然后在array[1...n-1]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。
至此，常用排序算法系列的文章结束，有什么问题欢迎指正和多多交流。