Leetcode详细解答

最新代码：https://github.com/krystism/leetcode

Algorithms

Database

Shell

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(24) Mar 22, 2016 04:05:55 PM

蓄水池抽样

什么是蓄水池抽样，它能解决什么问题?

从一次面试说起

百度面试以算法为主啊，手动写代码。第一道题是实现c语言库函数strcpy，这个原理很简单，但要注意以下这几点：

  • 空指针检查（包括src和dest）
  • 内存重叠，要检查指针是否重叠
  • 最后拷贝时，别忘了在dest追加字符串终结符号0
  • 如何保证dest已分配足够内存
  • 为什么从后向前拷贝？

第二道题是写一个类，实现堆的操作。说实话，虽然堆的操作不难，但要真正实现它并不容易。以下需要注意的点：

  • 泛型参数（泛化编程）
  • 类型必需可比较或者提供比较器
  • 不能实例泛型类型，即不能new T[]或者new T()，只能使用Object数组
  • 内存动态分配，内存拷贝（数组拷贝）

重点是第三道题目：给定一个文件，从中随机取出n行，并计算时间复杂度。我上来便是这样的代码：

import random
def sample(filename, n = 3):
    assert(filename is not None)
    result = []
    with open(filename) as f:
        lines = f.readlines()
    while len(result) < n :
        line = random.choice(lines)
        if line not in result:
            result.append(line.strip())
    return result

这种方法

  • 必须把文件内容全读入内存，如果文件很大怎么办？
  • 设N为文件行数，n和N接近时，越到后面，冲突越大，效率极低。
  • 有人说，先随机生成n个数构成一个集合A（还是有冲突哦），读取文件，当行数属于A时，取出该行，问题不就解决了？ 问题是文件总行数是多少？必须知道文件总行数才能知道随机数的取值范围啊。必须先扫描一遍文件？文件很大时这样的效率如何？

后来面试官问我知不知道分治法，我说了解，但这有关系么？文件分割建索引？全错！！！

蓄水池抽样

蓄水池抽样（Reservoir Sampling ）是一个很有趣的问题，它能够在o（n）时间内对n个数据进行等概率随机抽取， 例如：从1000个数据中等概率随机抽取出100个。另外，如果数据集合的量特别大或者还在增长（相当于未知数据集合总量）， 该算法依然可以等概率抽样。

以上摘自handspeaker博客

算法步骤为：

  1. 从文件中取前n行，结果集result
  2. 令i表示当前行数，c为当前行内容，m = random(1, i)，即m为1～i的一个随机数。
  3. 若m <= n, 则令result[m] = c，即替换第m行内容，否则舍弃c。
  4. 若已到文件结尾，退出算法，返回result，否则转2

利用归纳法可以证明每行被取的概率是相等的，证明过程 见handspeaker博客

回到问题

问题解决了，毫无悬念！

import random
def sample(filename, n = 5):
    assert(filename is not None)
    result = []
    with open(filename, mode = "r") as f:
        for i in range(n):
            line = f.readline()
            if line == '':
                return result
            else:
                result.append(line.strip())
        i = n
        for line in f:
            k = random.randint(0, i)
            if k < n:
                result[k] = line.strip()
            i += 1
    return result

 

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(87) Mar 22, 2016 04:03:09 PM

康托展开及其应用

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。

定义

公式为:

X = a[n - 1] * (n - 1)! + a[n - 2] * (n - 2)! + ... + a[0] * 0!,
其中, a[i]为整数，并且0 <= a[i] <= i, 0 <= i < n, 表示当前未出现的的元素
中排第几个。

比如31254,

  • 在3后面比3小的有2个，分别为1,2
  • 在1后面比1小的有0个
  • 在2后面比2小的有0个
  • 在5后面比5小的有1个，为4
  • 在4后面比4小的有0个

因此a数组序列为2 0 0 1 0

X = 2 * 4! + 0 * 3! + 0 * 2! + 1 * 1! + 0 * 0!
  = 2 * 24 + 1
  = 49

既然是双射关系那一定可以反推出来31254这个序列。 首先我们需要推出a序列。

  • 49 / 4! = 2,因此a[4] = 2, 此时49 % 4! = 1,
  • 1 / 3! = 1 / 2! = 0,因此a[3] = a[2] = 0,
  • 而 1 / 1 = 1, 因此a[1] = 1,1 % 1! = 0,
  • 0 / 0! = 0,因此a[0] = 0
  • 所以得到a数组为2 0 0 1 0

再由a数组推出序列，根据a数组的意义反推。

  • a[4] = 2, 表示它在1 2 3 4 5 序列中比它小的有2个，即它自己排第3，它等于3
  • a[3] = 0, 表示它在1 2 4 5序列中比它小的有0个，即最小数，等于1
  • a[2] = 0, 表示它在2 4 5 中最小，等于2
  • a[1] = 1, 表示它在4 5中比它小的有一个，即排第2,等于5
  • a[0] = 0, 表示它在4中最小，只能是4

因此序列为3 1 2 5 4

应用

一个直观的应用就是给定一个自然数集合和一个序列，求这个序列中按从小到大的顺序 排第几个?

比如1 2 3 4 5, 3 1 2 5 4比它小的序列有49个，即它排第50

另一个应用就是逆推第K个排列是多少，比如第50个全排列是多少？则首先减1得到49, 再反推即可得到3 1 2 5 4

另外在保存一个序列，我们可能需要开一个数组，如果能够把它映射成一个自然数， 则只需要保存一个整数，大大压缩空间.

计算

计算包括编码（根据序列求对应的自然数）和解码（康托展开）。

编码

static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int cantor(int *a, int n)
{
    assert(n < 10);
    int x = 0;
    for (int i = 0; i < n; ++i) {
        int smaller = 0;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[i])
                smaller++;
        }
        x += FAC[n - i - 1] * smaller;
    }
    return x;
}

解码

int decantor(int *a, int n, int k)
{
    int *num = malloc(sizeof(int) * n );
    int len = n;
    for (int i = 0; i < n; ++i)
        num[i] = i + 1;
    int cur = 0;
    for (int i = n - 1; i > 0; --i) {
        int index = k / FAC[i];
        k %= FAC[i];
        a[cur++] = num[index];
        listRemove(num, &len, index);
    }
    a[cur] = num[0];
    free(num);
    return 0;
}

 

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(6) Mar 22, 2016 04:01:30 PM

随机数和洗牌算法

什么是随机数？通俗说法就是随机产生的一个数，这个数预先不能计算出来的，并且所有可能出现的数字，概率应该是均匀的。因此随机数应该满足至少以下两点：

  1. 不可计算性，即不确定性。
  2. 机会均等，即每个可能出现的数字必须概率相等。

如何产生随机数是一个具有挑战的问题，一般使用随机硬件产生，比如骰子、电子元件噪声、核裂变等。

在计算机编程中，我们经常调用随机数产生器函数，但我们必须清楚的一点是，一般直接调用软件的随机数产生器函数，产生的数字并不是严格的随机数，而是通过一定的算法计算出来的（不满足随机数的不可计算性），我们称它为伪随机数！由于它具有类似随机的统计特征，在不是很严格的情况，使用软件方式产生伪随机相比硬件实现方式，成本更低并且操作简单、效率也更高！

那一般伪随机数如何产生呢？ 一般是通过一个随机种子（比如当前系统时间值），通某个算法（一般是位运算），不断迭代产生下一个数。比如c语言中的stdlib中rand_r函数（用的glibc）：

/* This algorithm is mentioned in the ISO C standard, here extended
   for 32 bits.  */
int
rand_r (unsigned int *seed)
{
  unsigned int next = *seed;
  int result;

  next *= 1103515245;
  next += 12345;
  result = (unsigned int) (next / 65536) % 2048;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  *seed = next;

  return result;
}

而java中的Random类产生方法next()为：

 protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

java中还有一个更精确的伪随机产生器java.security.SecurityRandom, 它继承自Random类，可以指定算法名称，next方法为：

 final protected int next(int numBits) {
        int numBytes = (numBits+7)/8;
        byte b[] = new byte[numBytes];
        int next = 0;

        nextBytes(b);
        for (int i = 0; i < numBytes; i++) {
            next = (next << 8) + (b[i] & 0xFF);
        }

        return next >>> (numBytes*8 - numBits);
    }

当然这个类不仅仅是重写了next方法，在种子设置等都进行了重写。

最近有一道题：已知一个rand7函数，能够产生1～7的随机数，求一个函数，使其能够产生1～10的随机数。

显然调用一次不可能满足，必须多次调用！利用乘法原理，调用rand7() * rand7()可以产生1~49的随机数，我们可以把结果模10（即取个位数）得到0~9的数，再加1,即产生1~10的数。但我们还需要保证概率的机会均等性。显然1～49中，共有49个数，个位为0出现的次数要少1，不满足概率均等，如果直接这样计算，2~10出现的概率要比1出现的概率大！我们可以丢掉一些数字，比如不要大于40的数字，出现大于40,就重新产生。

int rand10() {
    int ans;
    do {
        int i = rand7();
        int j = rand7();
        ans = i * j;
    } while(ans > 40);
    return ans % 10 + 1;
}

随机数的用途就不用多说了，比如取样，产生随机密码等。下面则着重说说其中一个应用--洗牌算法。

我们可能接触比较多的一种情况是需要把一个无序的列表排序成一个有序列表。洗牌算法（shuffle）则是一个相反的过程，即把一个有序的列表（当然无序也无所谓）变成一个无序的列表。

这个新列表必须是随机的，即原来的某个数在新列表的位置具有随机性！

我们假设有1～100共100个无重复数字。

很容易想到一种方案是：

    从第一张牌开始，利用随机函数生成器产生1～100的随机数，比如产生88,则看第88个位置有没有占用，如果没有占用则把当前牌放到第88位置，如果已经占用，则重新产生随机数，直到找到有空位置！

    首先必须承认这个方法是可以实现洗牌算法的。关键在于效率，首先空间复杂度是O(n)，时间复杂度也是O(n)，关键是越到后面越难找到空位置，大量时间浪费在求随机数和找空位置的。

第二中方案：

    从第一张牌开始，设当前位置牌为第i张，利用随机函数生成器产生1～100的随机数，比如产生88，则交换第i张牌和第88张牌。

这样满足了空间是O（1）的原地操作，时间复杂度是O(n)。但是否能够保证每个牌的位置具有机会均等性呢？

首先一个常识是：n张牌，利用随机数产生N种情况，则必须满足N能够整除n，这样就能给予每个牌以N/n的机会（或者说权值），如果N不能整除n，必然机会不均等，即有些牌分配的机会多，有些少。

我们知道100的全排列有100的阶乘种情况，而调用100次随机函数，共可以产生100^100种情况，而n^n 必然不能整除n!，具体证明不在这里叙述。

那我们可以利用第二种方法改进，每次不是产生1~100的随机数，而是1~i的数字，则共有n!中情况，即N=n!，显然满足条件，且时间为O(n),空间为O(1).这也就是Fisher-Yates_shuffle算法，大多数库都使用的这种方法。

我们看看java中Collections实现：

 public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

除了首先判断能否随机访问，剩下的就是以上算法的实现了。

STL中实现：

// random_shuffle

template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
                           _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __random_number((__i - __first) + 1));
}

template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
                    _RandomNumberGenerator& __rand) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __rand((__i - __first) + 1));
}

如何测试洗牌算法具有随机性呢？其实很简单，调用洗牌算法N次，牌数为n，统计每个数字出现在某个位置的出现次数，构成一个矩阵n * n,如果这个矩阵的值都在N/n左右，则洗牌算法好。比如有100个数字，统计一万次，则每个数字在某个位置的出现次数应该在100左右。

洗牌算法的应用也很广，比如三国杀游戏、斗地主游戏等等。讲一个最常见的场景，就是播放器的随机播放。有些播放器的随机播放，是每次产生一个随机数来选择播放的歌曲，这样就有可能还没有听完所有的歌前，又听到已经听过的歌。另一种就是利用洗牌算法，把待播放的歌曲列表shuffle。如何判断使用的是哪一种方案呢？ 很简单，如果点上一首还能回去，则利用的是洗牌算法，如果点上一首又是另外一首歌，则说明使用的是随机产生方法。比如上一首是3,现在是18,点上一首，如果是3说明采用的洗牌算法，如果不是3，则说明不是洗牌算法（存在误判，多试几次就可以了）。

顺便提一下网上的一些抽奖活动，尤其是转盘，是不是真正的随机？答案留给看客！

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(8) Oct 25, 2014 09:50:24 AM

小米2013年招聘笔试算法题--朋友圈

题目描述：假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。 最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

显然本质就是求无向图的连通分量个数。而要求连通分量数，就是遍历图的过程。遍历完所有节点，需要调用遍历几次就是连通分量个数。比如题目中使用DFS，从节点1出发，可以遍历节点2,3,而要遍历完所有节点还需从节点4出发，再遍历一次，共遍历两次，因此连通分量数为2。实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10000
char map[N][N];
char used[N];
void dfs(int i, int n)
{
	int j;
	used[i] = 1;
	for(j = 1; j <= n; j++) {
		if (map[i][j] && !used[j])
			dfs(j, n);
	}
}
/* 判断是否存在未访问节点
 * 若存在，则返回第一个未访问节点编号
 * 若不存在，则返回-1
 */
int isVisitedAll(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		if (used[i] == 0)
			return i;
	return -1;
}
int main(int argc, char **argv)
{
	int n, m;
	int a, b, i, sum, cur;
	while (scanf("%d%d", &n, &m) != EOF) {
		if (n == 0)
			break;
		memset(map, 0, sizeof(map));
		memset(used, 0, sizeof(used));
		sum = 0;
		for (i = 0; i < m; i++) {
			scanf("%d%d", &a, &b);
			map[a][b] = map[b][a] = 1;
		}
		while((cur = isVisitedAll(n)) != -1) {
			sum++;
			dfs(cur, n);
		}
		printf("%d\n", sum);
	}
	return 0;
}

暂且不说时间复杂度吧，空间复杂度就足够吓人了。首先需要一个表示图的01矩阵，大小为O(n  * n), 还需要记录是否节点是否已经被访问，需要大小为O(n)的空间。

换一种思路，其实根据题目朋友圈，我们就应该想到每一个圈其实就是一个集合，存在关系的，归为一个集合中，最后即需要求有多少个不相交的集合即有多少个圈子。由此不难想出，这其实就是并查集。不了解并查集可以查看维基百科并查集

想到了并查集，不难写出代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
int father[N];
void init(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		father[i] = i;
}
int getFather(int v)
{
	if (father[v] == v)
		return v;
	else {

		father[v] = getFather(father[v]);
		return father[v];
	}
}
void merge(int x, int y)
{
	int fx = getFather(x);
	int fy = getFather(y);
	if (fx < fy)
		father[fx] = fy;
	else
		father[fy] = fx;
}
int same(int x, int y)
{
	return getFather(x) == getFather(y);
}
int main(int argc, char **argv)
{
	int n, m;
	int a, b;
	int i;
	int sum;
	while (scanf("%d%d", &n, &m) != EOF) {

		if (n == 0)
			break;
		init(n);
		sum = 0;
		for (i = 1; i <= m; i++) {
			scanf("%d%d", &a, &b);
			merge(a, b);
		}
		for (i = 1; i <= n; i++) {
			if (getFather(i) == i)
				sum++;
		}
		printf("%d\n", sum);
	}
	return 0;
}

显然空间大大减少了，只需要O(n)的空间。

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(0) Oct 28, 2013 04:55:50 PM

求数对之差最大值

给定一个数组a, 长度n，索引从0开始，定义数对之差为a[i] - a[j], 其中0 <= i < j < n，即数组前面的数减去数组后面任意一个元素。现在要求数对之差的最大值。如数组int a[] = {2, 4, 1, 16, 7, 5, 11, 9}，数对之差最大值为11, 16 - 5 的结果。

最直接的方法就是暴力枚举法，即求出所有的数对之差，这样的时间复杂度为O(n2)。那有没有更高效的方法呢？

其实这个和求数组最大连续和有点类似，我们知道如果减少不变，被减数越大，则差越大。于是我们利用动态规划的思想，假定减数固定为数组某个元素，设为a[i]，那么与a[i]形成的数对之差最大值就是a[i]前面的最大值（这个最大值我们可以保存在一个临时变量中）减去a[i]的值，我们可以依次遍历整个数组，分别求出与这个元素作为减数的最大数对之差，他们的最大值即为所求。这样只需要遍历数组一遍，时间复杂度为O(n)。附上代码：

#include <stdio.h>
#include <assert.h>
#include <limits.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
static int maxDiff(const int *a, const int n)
{
	assert(a != NULL && n > 1);
	int cur_diff, i;
	int max_diff = INT_MIN;
	int max = INT_MIN;
	for (i = 1; i < n; i++) {
		max = MAX(max, a[i - 1]);
		cur_diff = max - a[i];
		max_diff = MAX(max_diff, cur_diff);
	}
	return max_diff;
}
转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(0) Oct 25, 2013 03:24:17 PM

求不相交的两个子数组的最大连续和

求一个数组的两段连续的部分的最大和，例如1,-2,2,3,-4，结果就是6，第一段就是1，第二段就是2,3。而数组-2,3,-1,2,-5,-6,7,-3,4,-9,2,1，第一段是3,-1,2，第二段是7,-3,4，结果就是12。
这个其实就是数组最大连续和的扩展问题，经典DP问题。求最大连续和并不难，我们只需要遍历数组一次，并用一个dp[i]函数记录从数组开头到第i个元素的子数组的最大和，显然if i == 0, dp[i] = a[0], 而if i > 0, 需要考虑dp[i - 1] 的符号， 如果dp[i - 1] <= 0，则dp[i] = a[i]，因为前面i-1个元素最大连续和不大于0, 加上当前元素不可能大于当前元素，只会越加越小, 即小于a[i]。 而当dp[i - 1] > 0时， dp[i] = dp[i - 1] + a[i]，原因很简单，前面的连续和大于0, 加上当前元素a[i]，肯定会大于a[i]. 有了这个思路，算法就很简单了。这里时间复杂度是O(n),空间复杂度也是O(n),但我们发现我们只需要一个最大的和，那些前面算出的和，如果不是最大，根本没有必要保存，我们只需维护一个保存当前最大和的变量就可以了，因此空间复杂度可以降低为O(1)。
要求两段连续的部分和的最大值，可以先把数组分成两个各不相交的子数组，然后分别求子数组的最大连续和，相加最大即为所求。
附上代码：
/* coding=UTF-8 */
#include <stdio.h>
#include <limits.h>
#define MAX_LENGTH 1000
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int errno;
/* 求一维数组最大连续和 */
int max_subarray(int *a, int len)
{
	errno = 0;
	if (NULL == a || len < 1) {
		errno = 1;
		return 1;
	}
	int max = a[0], i, sum = a[0];
	for (i = 1; i < len; i++) {
		if (sum < 0) {
			sum = a[i];
		} else {
			sum += a[i];
		}
		max = MAX(max, sum);
	}
	return max;
}
/* 求一个数组的两段连续的部分的最大和
 * 输入一个数组a，以及长度len
 * 思路：先把a分成前后两部分，分别求两部分的最大连续和
 * 依次遍历求得两个子数组的最大连续和最大即为所求
 */
int op(int *a, int len)
{
	errno = 0;
	/* 输入异常处理 */
	if (NULL == a || len < 2) {
		errno = 1;
		return 0;
	}
	int i, max = INT_MIN;
	for (i = 1; i < len; i++) {
		int t1 = max_subarray(a + i, len - i);
		int t2 = max_subarray(a, i);
		max = MAX(max, t1 + t2);
	}
	return max;
}
int main(int argc, char **argv)
{
	int a[] = {1,-2,2,3,-4};
	int b[] = {-1, -1, -1, -1};
	int c[] = {-1, 1};
	printf("%d\n", op(a, 5));
	printf("%d\n", op(b, 4));
	printf("%d\n", op(c, 2));
	return 0;
}

 

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

algorithm Comments(1) Oct 16, 2013 07:54:10 PM

堆排序c语言实现

昨天面试，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/若有错误，请多多指正，谢谢！

algorithm Comments(0) Aug 16, 2013 11:36:19 AM