【算法】（C语言）：堆排序

堆（二叉树的应用）：

• 完全二叉树。
• 最大堆：每个节点比子树所有节点的数值都大，根节点是最大值。
• 父子索引号关系（根节点为0）：（向上）子节点x，父节点(x-1) // 2。（向下）父节点x，左子节点2x+1，右子节点2x+2。
• 一般用数组实现堆。

堆排序：

第一步、构建堆（最大堆）。

1. 找到最后的父节点：(最后元素的索引号-1) // 2。
2. 从最后的父节点到根节点，依次向下调整（比较父节点和左右子节点，最大值为父节点）。
3. 最终，根节点为最大值。尾指针指向最后节点。

第二步、排序

1. 交换根节点和尾指针所在节点。此时，尾指针所在节点为目前正在排序中数据的最大值，保持不动。
2. 尾指针向前（向左）移动一位。
3. 从根节点到尾指针所在节点，依次向下调整。
4. 此时，根节点为目前正在排序中数据的最大值（不包含已排序好且保持不动的最大值）。

第三步、重复第二步，直到尾指针指向根节点停止。

时间复杂度：O(nlogn)

• 初次构建堆，时间约n。
• 每次向下调整，都是使用2x+1、2x+2，遍历次数是logn（对数），几乎每个元素都要重排，因此时间约 nlogn。
• 相对于nlogn而言，n可忽略，即总时间O(nlogn)。

空间复杂度：O(1)

• 在原位置排序，只重复使用了用于交换的临时空间，不随数据量的变动而变动，空间使用为常量(1)。

---

C语言实现思路：

先构建堆（最大堆），再排序。

void heapsort(int *array, int length)		// heap sort
{// 构建堆（最大堆）// 找到最后的父节点int i = ceil((length - 1) / 2);	// 从最后的父节点到根节点，依次向下调整（父子节点比较大小，最大值为父节点）for(; i >= 0; i--){adjustdown(array, i, length - 1);}// 排序// 交换根节点和尾指针所在节点，尾指针前移一位，从根节点开始向下调整for(int n = length - 1; n > 0; n--){swap(&array[0], &array[n]);adjustdown(array, 0, n - 1);}
}

因多次向下调整，多次交换两个数据，因此，向下调整、交换数据分别用函数单独实现。

交换两个数据：

传入的参数为数据的内存地址，将直接在内存地址进行数据交换。

void swap(int *a, int *b)
{int tmp = *a;*a = *b;*b = tmp;
}

向下调整：

向下在左右子节点中找到较大值的节点，父节点再与较大值的子节点比较大小，若子节点数值更大，父子节点交换位置。 

void adjustdown(int *array, int start, int end)		// adjust the heap down
{while(start < end){int left = 2 * start + 1, right = 2 * start + 2, maxchild;// 比较左右子节点，找到较大值的子节点if(left > end) break;if(right <= end && array[left] < array[right]) maxchild = right;else maxchild = left;// 与较大值的子节点比较，若子节点数值更大，交换父子节点的位置if(array[start] < array[maxchild]){swap(&array[start], &array[maxchild]);start = maxchild;}else break;}
}

---

完整代码：（heapsort.c）

#include <stdio.h>
#include <math.h>/* function prototype */
void heapsort(int *, int);	// heap sort
void traverse(int *, int);	// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);heapsort(arr, n);	printf("[ after heap sort ] ");traverse(arr, n);return 0;
}/* subfunction */
void swap(int *a, int *b)		// change the value of two datas
{int tmp = *a;*a = *b;*b = tmp;
}void adjustdown(int *array, int start, int end)		// adjust the heap down
{while(start < end){int left = 2 * start + 1, right = 2 * start + 2, maxchild;// left child or right child, find the max oneif(left > end) break;if(right <= end && array[left] < array[right]) maxchild = right;else maxchild = left;// parent compair with maxchild, if smaller than maxchild,change the positionif(array[start] < array[maxchild]){swap(&array[start], &array[maxchild]);start = maxchild;}else break;}
}void heapsort(int *array, int length)		// heap sort
{// build a heapint i = ceil((length - 1) / 2);			// find the last parent// from the last parent to 0 index, cycle ajust the heap down(parent compair with child)for(; i >= 0; i--){adjustdown(array, i, length - 1);}// sort (root is max, change max to the last, end pointer move a step to the left)for(int n = length - 1; n > 0; n--){// swap the first and last elementswap(&array[0], &array[n]);// from 0 index, compair with left child and right child, max is parentadjustdown(array, 0, n - 1);}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

编译链接： gcc -o heapsort heapsort.c

执行可执行文件： ./heapsort