int main(void){
vector v;
for( int i = 0; i < 100; i++ )
v.push_back( rand() );
sort( v.begin(), v.end() );
for( int i = 0; i < 100; i++ )
cout << v[i] << endl;
return 0;
}
c++中的set容器也可以实现排序的功能，当元素添加到集合中后，set可以自动排序。用迭代器从头到尾遍历就可以得到排序序列。参考：http://www.cplusplus.com/reference/stl/set/
python中列表有sort方法。
list = [3,4,5,6,7]
list.sort()
2.位向量的实现就是用比特位0,1来表示一些特定信息，通常是用数组，每个int中包含32个bits，当我们定位某个位置时，先确定索引是在哪个int中，然后再确定int中的那个位对应索引。我用c语言和c++中的类实现了位向量。我不帖出来了，在github上，https://github.com/fookwood/fkcode/tree/master/bitvector，排版看起来不行= =。。。
c++中有现成的bitset，我猜实现原理应该和以上差不多。
3.位图的实现我用了三种，一个是c语言的（简称cvec），一个是c++的（简称cppvec），还有时c++现成的bitset（简称bitset）。系统排序用的是sort命令，加上-n选项。排序用了c的qsort，c++的sort和c++的set。下面是运行时间。
cvec 1.737 1.001
cppvec 1.769 1.033
bitset 2.644 1.908
系统sort命令 5.290 4.554
qsort 2.081 1.345
sort 2.802 2.066
set 5.921 5.185
输入输出的时间是0.736s。左右分别为带输入输出和不带的。
可以看出两种语言位图的实现都是效率最高的，c++中的bitset，set，sort虽然效率上差了点，但是实现上非常方便，而且能保证一定的正确性。系统的排序实在方便，一句命令就可以搞定( sort -n < in -o out ).
4.生成[0,n)的之间k个不重复的随机整数。
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10000000;
const int K = 10000000;
int randint( int l, int r ){
return rand() % ( r-l ) + l;
}
int a[ N ];
int main(void){
for( int i = 0; i < N; i++ )
a[i] = i;
for( int i = 0; i < K; i++ ){
swap( a[i], a[ randint(i,N) ] );
printf("%d\n",a[i]);
}
return 0;
}
如果要想生成这样一个数组，可以直接从头到尾循环，每个数根随机位置交换值就可以。
5.可以将输入文件分成两分，第一份保存[0,5000000)的数，第二个文件保存[5000000,10000000)的数字，然后分别进行排序，所用内存就可以降到1MB以内。如果我们把文件分成k份（每份都存一定区间的数），那么就可以在n的时间，n/k的空间内完成排序。标准答案中说可以在nk时间n/k空间内完成，我对于nk的时间不太明白，把输入文件扫描，然后把数字保存到相应文件，扫一遍应该就可以了。
6.每个整数最多出现10次，那么保存每个数字信息的空间不再是1bit了，可以用4bits来保存，可以类比第五题，可以分成4份，在n/4的空间内完成。同样，当保存数字信息的量变化时，分成更多份，就可以在更小的空间内完成。
7.
数出现超过一次？
当第二次更新的时候，相应位已经是1了，这个时候提示错误。
当输入小于0或者大于等于n？
当输入数字时候对其进行范围判断，忽略或者提示错误。
不是数值？
忽略
8.题目描述中排序包含区号么。。。用一种效率稍逊的算法就是每个区号建立一个set，查找时候的效率是O(logN)的。有木有谁又更好的办法。
9.本题值得一说。
初始化空间需要大量时间，不过我们的应用只需要其中一点点空间，比如1000000的位图，我们只用到其中的10位，怎样节省时间？题目中提示，可以用额外的正比于向量大小的空间。我当时直接看的答案，到晚上搜了搜才看懂。
10.类似于取快递，根据电话号码的最后一位或者最后两位进行分类，类似于哈希的思想，用顺序遍历来处理碰撞。不能用开头的原因是很多电话号码的前面都是一样的，比如手机号码都是以1开头的。而且最后一位的分布比较随机、均匀。
11.= =答案竟然说飞鸽传书。
12.铅笔? T.T ….
飘过，膜拜。。。
交换个链接吧。。我已经加了你的。我的是http://acm.zhihua-lai.com
😉 😉
楼主啊第6题 分为四份 是根据什么来分啊 ❓
2^4大于10，可以用4个位来存储10个数
第五题，每次读取时，判断读到的数字是否是本次排序范围之内的，如果是，就排序，否则就丢弃读到的这个数字，也不需要把大文件分割成小文件，不存在分割这个事情，，每趟排序都需要读取n个 数据，所以时间开销是nk，
我大概想到的为代码：
#define N 10000000
#define k 5
#define RANGE N/K
int array[1+range/32];
for(i=0;i<k;i++)
{
while(scanf("%d",¤tNum)!=EOF)
{
if(i*RANGE<=currentNum<=(i+1)*RANGE)
{
排序;
输出到文件;
}
}
}
你的这个思路个人感觉有点问题，遇到不在i*RANGE<=currentNum<=(i+1)*RANGE的数字丢弃不进入排序，那被丢弃的数什么时候被排序，目测应该没有第二次机会输入了吧。
第八题可以用第六题的方法，只不过是用3个bit来存信息，000代表无，001代表800, 010代表另一个,100代表另另一个，当800时 | 001,同样 其他 |010 和 100，就可以判断这个号是否存在，并且都有哪些存在.如111代表三个都有。
你好！第四题，生成[0,n)的之间k个不重复的随机整数。
int randint( int l, int r ){
return rand() % ( r-l ) + l;
}
这个代码是返回l到r-1直接的任意数字，前后都是闭区间。
这样的话，在主函数里面如下，第二次循环的时候会不会重复呢？
int main(void){
for( int i = 0; i < N; i++ )
a[i] = i;
for( int i = 0; i < K; i++ ){
//这里。我怎么感觉randint那个函数后面再加个1，才不会重复呢。
swap( a[i], a[ randint(i,N) ] );
printf("%d\n",a[i]);
}
return 0;
}
求指正，谢谢。