其实就是随机洗牌。
Knuth给过一个算法，为代码如下：
注意：随机数不是1~n，而是i~n！！
For i = 1 to n
Pick a random integer j from i to n
Swap A[i] and A[j]
关于为什么如此，吾等码农就不了解了，等大神来证明吧……[......]
关于Random Shuffling算法。
1 Reply
Category Archives: 算法&数据结构
大量数据取k个最大值并排序
需求是这样的，我们都知道，在信息检索中，经常要取top-k(一共k，而不是第k)个得分最大的文档，并且从大到小排序。
而且文档规模很大，最少也要上千万。
话说这是一道很可以拿来面试的题啊。
我们不考虑Hadoop神马的，就说说单机怎么搞。
最傻的做法就是把1000万个都存储下来，然后sort，然后取min(k, vec.size())。
这样有两个缺点：
1、内存占用非常大，其实我们只要保留最大的1000个，但这样就要保存N个。在1000万的测试中，它要占用68M[......]
多路归并算法(K-Way Merge Algorithm)
多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
(1)假设有K路数据流，流内部是有序的，且流间同为升序或降序
(2)首先读取每个流的第一个数，如果已经EOF，pass
(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个
(4)直到所有K路都EOF
代码如下：
/*
* main.c
*
* Created on: 20[......]
算法技术手册 – 查找 – 散列查找(Hash查找)
对于含有n个元素的集合C，我们先构造一个Hash函数，让n映射到b个桶内，当选择合理时，速度会很快，时间复杂度O(1)。
完美哈希函数：不会产生冲突，是存在的。
对于>=1个值映射到同一个桶的情况下，就会发生碰撞。处理方法：
- 链表：每个桶拉一个链表，第一遍散列后，在链表中查找是否存在元素。
- 开放定址：构造双变量散列函数h(u, j)。h(u, 0) = h(u)，此时退化为原始散列函数。
开放定址，分两类：
- 线性探测h(u, j)=(h(u)+j) m[......]
算法技术手册 – 查找 – 二分查找
二分查找，要求集合是有序的，在这个条件基础上，它比顺序查找具有更好的性能。
如果使用伴随数组，只需要struct中有一个key是有序的就行。
需要指出的是，当数组放在磁盘上时，时间复杂度就不再是O(LogN)，而取决于磁盘存取的开销。
源代码：
#include <stdio.h>
typedef int TYPE;
int search(TYPE* arr, int n, int t)
{
int low = 0;
int hi[......]