堆排序c语言实现

int32位 posted @ Aug 16, 2013 11:36:19 AM in algorithm , 2749 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

昨天面试,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;
}
调用heap_sort即可实现排序。
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter