昨天面试，5分钟手写堆排序，虽然以前写过这个算法，但面试时有点紧张，主要是用笔写，而且面试官一直盯着。。。。

回来自己再写了遍。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20

static inline int swap(int *a, int *b)
{
	int t = *a;
	*a = *b;
	*b = t;
	return 0;
}
/* 调整当然节点 */
static int adjust(int *a, int i, const int n)
{
	int lchild = i * 2 + 1, rchild = i * 2 + 2; /* 数组从0索引，因此左孩子索引为i * 2 + 1 */
	int min = i; /* 保存当然节点、左右孩子节点的最小值索引 */
	if (lchild < n && a[min] > a[lchild]) min = lchild;
	if (rchild < n && a[min] > a[rchild]) min = rchild;
	if (min != i) {
		swap(&a[min], &a[i]);
		adjust(a, min, n);
	}
	return 0;
}

/* 最小堆化 */
static int min_heapify(int *a, const int n)
{
	int i;
	for (i = n - 1; i >= 0; i--)
		adjust(a, i, n);
	return 0;
}
/* 堆排序，a为排序前数组，调用后，a变为已排好序的数组 */
static int heap_sort(int *a, const int n)
{
	int i;
	for (i = 0; i < n; i++) {
		min_heapify(a + i, n - i);
	}
}
int main(int argc, char **argv)
{
	int a[N], i;
	srandom(time(NULL));
	for (i = 0; i < N; i++)
		a[i] = random() % 100;
	for (i = 0; i < N; i++)
		printf("%d ", a[i]);
	printf("\n");
	heap_sort(a, N);
	for (i = 0; i < N; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}

• 相关文章
• 全局相关文章