1、各种排序，是否稳定什么的
(1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个 元素 比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无 聊地 把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换 把两 个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排 序是 一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的， 在剩 余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不 用选 择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元 素小 ，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破 坏了 。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换 ，那 么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法 。 (3)插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚 开始 这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始， 也就 是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面， 否则 一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元 素把 想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序 序列 出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 (4)快速排序 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]， 其中 center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直 往左 走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j], 重复 上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元 素和 a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打 乱， 所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻 。 (5)归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接 有序 )或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列， 不断 合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个 元素 如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的 过程 中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时 ，我 们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归 并排 序也是稳定的排序算法。 (6)基数排序 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类 推， 直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级 排序 ，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序 基于 分别排序，分别收集，所以其是稳定的排序算法。 (7)希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步 长最 大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入 排序 对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多 次插 入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同 的插 入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱 ，所 以shell排序是不稳定的。 (8)堆排序 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于 其2 个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序 的过 程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素 之间 的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时 ，就 会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个 父节 点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了 。所 综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而 冒泡 排序、插入排序、归并排序和基数排序是稳定的排序算法。 2、内存泄露
3、系统调用vs函数调用
从程序完成的功能来看，函数库提供的函数通常是不需要操作系统的服务. 函数是在用户空间内执行的，除非函数涉及到I/O操作等，一般是不会切到核心态的。系统调用是要求操作系统为用户提供进程，提供某种服务，通常是涉及系统的硬件资源和一些敏感的软件资源等。 函数库的函数，尤其与输入输出相关的函数，大多必须通过Linux的系统调用来完成。因此我们可以将函数库的函数当成应用程序设计人员与系统调用程序之间的一个中间层，通过这个中间层，我们可以用一致的接口来安全的调用系统调用。这样程序员可以只要写一次代码就能够在不同版本的linux系统间使用积压种具体实现完全不同的系统调用。至于如何实现对不同的系统调用的兼容性问题，那是函数库开发者所关心的问题。 从程序执行效率来看，系统调用的执行效率大多要比函数高，尤其是处理输入输出的函数。当处理的数据量比较小时，函数库的函数执行效率可能比较好，因为函数库的作法是将要处理的数据先存入缓冲区内，等到缓冲区装满了，再将数据一次写入或者读出。这种方式处理小量数据时效率比较高，但是在进行系统调用时，因为用户进程从用户模式进入系统核心模式，中间涉及了许多额外的任务的切换工作，这些操作称为上下文切换，此类的额外工作会影响系统的执行效率。但是当要处理的数据量比较大时，例如当输入输出的数据量超过文件系统定义的尽寸时，利用系统调用可获得较高的效率。 从程序的可移植性的角度来看，相对于系统调用，C语言的标准备函数库（ANSI C） 具备较高的可移植性，在不同的系统环境下，只要做很少的修改，通常情况是不需要修改的 4、虚函数
5、长连接、短连接的
所谓长连接，指在一个TCP连接上可以连续发送多个数据包，在TCP连接保持期间，如果没有数据包发送，需要双方发检测包以维持此连接，一般需要自己做在线维持。 短连接是指通信双方有数据交互时，就建立一个TCP连接，数据发送完成后，则断开此TCP连接，一般银行都使用短连接。 比如http的，只是连接、请求、关闭，过程时间较短,服务器若是一段时间内没有收到请求即可关闭连接。 其实长连接是相对于通常的短连接而说的，也就是长时间保持客户端与服务端的连接状态。
长连接与短连接的操作过程
通常的短连接操作步骤是： 连接→数据传输→关闭连接；
而长连接通常就是： 连接→数据传输→保持连接(心跳)→数据传输→保持连接(心跳)→……→关闭连接； 这就要求长连接在没有数据通信时，定时发送数据包(心跳)，以维持连接状态，短连接在没有数据传输时直接关闭就行了
1.项目经历（讲清楚啊一定） 2.写strcpy函数 注意：字符串是否为空；字符串结尾是\0而不是\n；复制之前应判断源字符串和目标字符串的内存对齐。 3. 写一个TCP连接的程序？如何进行一个TCP连接？Http和TCP的关系？ 4.C++ Map实现了什么数据结构？ dequex是什么？ 为什么数据结构中的堆和操作系统中的堆都叫做堆呢？
为什么数据结构中的堆和操作系统中的堆都叫做堆呢？数据结构中的堆： 堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权。 (严蔚敏的数据结构中介绍的堆是在堆排序中。把堆顶元素与最后一个元素替换，然后输出最后一个元素（即交换前的堆顶）；然后调整堆。) 堆性质：叶子节点小于（或大于）父亲节点，则为小（大）顶堆。 数据结构中的堆可以用一个数组来存储（完全二叉树结构。） 操作系统中的堆： 这里的堆是属于内存分配方式的一种：动态分配内存。 实现的方式更接近于链表。堆内存中有很多块内存，可能不是连续的。所有需要用链表来组织。 在分配的时候，有多种策略。 首先查找是否有空闲的并且满足大小的堆内存，然后把最大的那块给需求者。 这里有点像数据结构中堆的优先权。C++
如何实现搜索中出现的搜索结果之外的近似搜索结果？
read和fread的区别？同类xxx和fxxx的区别？
快速排序，堆排序； tcp三次握手； 数据库索引； 关键路径； 线程同步； 线程死锁； 空格为token大字符串为小字符串 Socket通信过程 Apache 404错误的意思 给两个数组，无序，从中找出相同数并输出，时间复杂度等等 1.oracle和mysql有什么区别,分别用这两种数据库语句用select语句返回查询结果的前80条 2.给一个字符串数组,规定:abc = acb = bca...也就是与顺序无关,且每个字符串中一个字符最多出现一次,然后有一个文件,里面有很多的字符串,每行一个,统计字符串数组中的字符串在文件中出现的次数 1 字符串翻转 如“abcd” “dcba” 2 strcpy 函数 3 N个数中找出第M大的数（复杂度不能为O（N^2）） c++虚函数如何实现 二分法查找 算法时间复杂度 1.虚函数表放在哪个位置。 2.map的底层数据结构 1.socket编程 2.三次握手 3.字符串反转 1，实现iterator的前置++和后置++ 2，从100万个数中找最大的5个，时间复杂度不能超过2×N，不能用堆 编程：编写函数，去掉字符串前后的空格；两个有序链表合并成一个有序链表 海量数据：20w个词库，搜索结果中有敏感词不予以显示，如何实现；负载均衡 --------- 1，实现 void memcpy(const char* src, char* dest, size_t n); 2，128G长整型数据（8 Bytes）, 1G内存，2.5T硬盘，排序 3，找错, 程序如果能运行会出现什么错误。 int main(int argc, char** argv){ int i =0; int A[9]; for( ; i<10; i++){ A[i] = 0; } return 0; } 4， 1千万 URL,设计算法，对其压缩和解压缩，要求给出时间复杂度和空间复杂度。 5，董事长过生日。某公司为树形架构，董事长过生日，要求每位出席的员工都带一份礼物。但有以下要求：1，若某位领导出席，他的直接下属可以选择参加和不参加；2，若某位领导不出席，则其直接下属必须参加。 现要求设计一个算法，求出怎样发送邀请函使得董事长获得最多的礼物。 附加题： 1， 找错 class A{ A(){}; virtual ~A()=0; }; class B : public A{ B(){}; int doit(){ return printf("in class B); } virtual ~B(){ doit(); } }; class runner{ A* a; runner(){} void run(A* aa){ a = aa; a->doit(); } ~runner(){ a->doit(); a = NULL; } }; int main( int argc, char** argv){ B b; runner r; r.run(&b); return 0; } 2,算法题 struct Node{ Node* next; Node* rand;//rand 指向rand_list中随机的一个Node void* data; } rand_list; 实现 void copy( Node** to, Node* from); ------- 2,算法题 struct Node{ Node* next; Node* rand;//rand 指向rand_list中随机的一个Node void* data; } rand_list; 实现 void copy( Node** to, Node* from); 如果不用辅存，怎么实现？ struct Node{ Node* next; Node* rand;//rand 指向rand_list中随机的一个Node void* data; } rand_list; void copy( Node** to, Node* from) { Node *p, *np, *next; if (from == NULL) { *to = NULL; return; } // 第一遍：建链，新旧节点交替形成新的单链表 p = from; while (p) { next = p->next; np = new Node; np->data = p->data; np->next = next; p->next = np; p = next; } // 第二遍：赋值，给新节点的随机指针赋值 p = from; while (p) { p->next->rand = p->rand->next; p = p->next->next; } // 第三遍：还原，由一条单链表还原新旧两条单链表 *to = from->next; p = from; np = *to; p->next = np->next; p = np->next; while (p) { np->next = p->next; np = np->next; p->next = np->next; p = np->next; } } -- 新建一个链表to，除rand域外（先不用管），其余的与平常的链表复制无异。再把to 与from 想合并。形式为：from1->to1->from2->to2....再把from1->rand->next 赋给 from1->next->rand即可。然后再拆分to 和from. -- 另外一种解法 1先根据next指针复制一次新的链表，复制时新链表节点的random指针指向对应原节点，原节点的next指针指向新节点。这个过程会破坏原链表的 next。 2对新链表节点查找random。遍历一次新链表， New->random = new->random->random->next; 另外要恢复原链表的next，old->next = new->next->random; 链表扫两次。 -- c++ 虚函数的实现机制：笔记 收藏 1、c++实现多态的方法 其实很多人都知道，虚函数在c++中的实现机制就是用虚表和虚指针，但是具体是怎样的呢？从more effecive c++其中一篇文章里面可以知道：是每个类用了一个虚表，每个类的对象用了一个虚指针。具体的用法如下： class A { public: virtual void f(); virtual void g(); private: int a }; class B : public A { public: void g(); private: int b; }; //A，B的实现省略 因为A有virtual void f（），和g（），所以编译器为A类准备了一个虚表vtableA，内容如下： A::f 的地址 A::g 的地址 B因为继承了A，所以编译器也为B准备了一个虚表vtableB，内容如下： A::f 的地址 B::g 的地址 注意：因为B::ｇ是重写了的，所以B的虚表的g放的是B::g的入口地址，但是f是从上面的A继承下来的，所以f的地址是A::f的入口地址。 然后某处有语句 B bB;的时候，编译器分配空间时，除了A的int a，B的成员int b；以外，还分配了一个虚指针vptr，指向B的虚表vtableB，bB的布局如下： vptr ： 指向B的虚表vtableB int a： 继承A的成员 int b： B成员 当如下语句的时候： A *pa = &bB; pa的结构就是A的布局（就是说用pa只能访问的到bB对象的前两项，访问不到第三项int b） 那么pa->g()中，编译器知道的是，g是一个声明为virtual的成员函数，而且其入口地址放在表格（无论是vtalbeA表还是vtalbeB表）的第2项，那么编译器编译这条语句的时候就如是转换：call *(pa->vptr)[1]（C语言的数组索引从0开始哈~）。 这一项放的是B：：g()的入口地址，则就实现了多态。（注意 bB的vptr指向的是B的虚表vtableB） 另外要注意的是，如上的实现并不是唯一的，C++标准只要求用这种机制实现多态，至于虚指针vptr到底放在一个对象布局的哪里，标准没有要求，每个编译器自己决定。我以上的结果是根据g++ 4.3.4经过反汇编分析出来的。 2、两种多态实现机制及其优缺点 除了c++的这种多态的实现机制之外，还有另外一种实现机制，也是查表，不过是按名称查表，是 smalltalk等语言的实现机制。这两种方法的优缺点如下： （1）、按照绝对位置查表，这种方法由于编译阶段已经做好了索引和表项 (如上面的call *(pa->vptr[1]） )，所以运行速度比较快;缺点是：当A的virtual成员比较多（比如1000个），而B重写的成员比较少（比如2个），这种时候，B的vtableＢ的剩下的998个表项都是放Ａ中的ｖｉｒｔｕａｌ成员函数的指针，如果这个派生体系比较大的时候，就浪费了很多的空间。 比如：ＧＵＩ库，以ＭＦＣ库为例，ＭＦＣ有很多类，都是一个继承体系；而且很多时候每个类只是１，２个成员函数需要在派生类重写，如果用Ｃ＋＋的虚函数机制，每个类有一个虚表，每个表里面有大量的重复，就会造成空间利用率不高。于是ＭＦＣ的消息映射机制不用虚函数，而用第二种方法来实现多态，那就是： （２）、按照函数名称查表，这种方案可以避免如上的问题；但是由于要比较名称，有时候要遍历所有的继承结构，时间效率性能不是很高。（关于ＭＦＣ的消息映射的实现，看下一篇文章） ３、总结： 如果继承体系的基类的virtual成员不多，而且在派生类要重写的部分占了其中的大多数时候，用Ｃ＋＋的虚函数机制是比较好的； 但是如果继承体系的基类的virtual成员很多，或者是继承体系比较庞大的时候，而且派生类中需要重写的部分比较少，那就用名称查找表，这样效率会高一些，很多的ＧＵＩ库都是这样的，比如ＭＦＣ，ＱＴ ---- 如何从最大的N个数中选出最大或者最小的n个数？ 这 个问题我前前后后考虑了有快一年了，也和不少人讨论过。据我得到的消息，Google和微软都面过这道题。这道题可能很多人都听说过，或者知道答案（所谓 的“堆”），不过我想把我的答案写出来。我的分析也许存有漏洞，以交流为目的。但这是一个满复杂的问题，蛮有趣的。看完本文，也许会启发你一些没有想过的解决方案（我一直认为堆也许不是最高效的算法）。在本文中，将会一直以寻找n个最“大”的数为分析例子。注：本文写得会比较细节一些，以便于绝大多数人都能看懂，别嫌我罗嗦:) Naive 方法： 首先，我们假设n和N都是内存可容纳的，也就是说N个数可以一次load到内存，存放在数组里。从最简单的情况开始，如果n=1，那么没有任何疑惑，必须要进行N-1次的比较才能得到最大的那个数，直接遍历N个数就可以了。如果n=2呢？ 当然，可以直接遍历2遍N数组，第一遍得到最大数max1，但是在遍历第二遍求第二大数max2的时候，每次都要判断从N所取的元素的下标是否等于 max1 的下标，这样会大大增加比较次数。 对此有一个解决办法，可以以max1为分割点将N数组分成前后两部分，然后分别遍历这两部分得到两个“最大数”，然后取二者中的最大者既可得到max2。 也可以遍历一遍就解决此问题，首先维护两个元素max1，max2（max1>=max2），取到N中的一个数以后，先和max1比，如果比 max1大（则肯定比max2大），直接替换max1，否则再和max2比较确定是否替换max2。采用类似的方法，对于n=2，3，4……一样可以处理。这样的算法时间复杂度为O（nN）。当n越来越大的时候（不可能超过N/2，否则可以变成是找N-n个最小的数的对偶问题），这个算法的效率会越来越差。但是在n比较小的时候（具体多小不好说），这个算法由于实现简单高效，且不存在递归调用等系统损耗，实际效率应该非常不错。 堆： 当n较大的时候采用什么算法呢？首先我们分析上面的算法，当从N中取出一个新的数m的时候，它需要依次和max1，max2，max3……maxn比较，一直找到一个比m小的maxx，用m来替换max x，平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇的堆。堆有以下好处： 1. 它是一个完全二叉树，树的深度是相同节点数的二叉树中最少的，维护效率较高； 2. 它可以通过数组来实现，而且父节点p的数组下标与左右孩子节点l，r的数组下标的关系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在计算机中2*s[p]这样的运算可以用一个左移1位操作来实现，十分高效。再加上数组可以随机存取，效率也很高； 3. 堆的Extract操作，也就是将堆顶元素拿走并重新调整堆的时间复杂度是O(logn)，这里n是堆的大小； 具体到我们的问题，如何具体实现呢？首先开辟一个大小为n的数组区A，从N中读入n个数填入到A中，然后将A维护成一个小顶堆。然后从N中取出下一个数，即第n+1个数m，将m与堆顶A[0]比较，如果m <= A[0]，直接丢弃m。否则应该用m替换A [0]。但此时A的堆特性可能已被破坏，应该重新维护堆：从A[0]开始，将A[0]与左右孩子节点分别比较（特别注意，这里需要比较“两次”才能确定最大 数，在后面我会根据这个来和“败者树”比较），如果A[0]比左右子节点都小，则堆特性能够保证，否则如左（右）节点最大，则将A[0]与左（右）节点交换，并继续维护左（右）子树。依次执行，直至叶子节点，堆中保留的n个数就是N中最大的n个数。这都是堆排序的基本知识，唯一的trick就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O（logn），总体的复杂度是O（Nlogn）这样一来，比起上面的O（nN），当 n足够大时，堆的效率肯定是要高一些的。当然，直接对N数组建堆，然后提取n次堆顶就能得到结果，而且其复杂度是O（nlogN）,当n较大时这样会高效很多。但是对于online数据就没办法了，比如N不能一次load进内存，甚至是一个流，根本不知道N是多少。 败者树： 有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。 败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树： 败者树的叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的“败者”（注意记录的是输的那一方），而优胜者则往上传递继续比较，直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的“败者”，也就是所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录 “败者”对应的叶子节点，具体的数值可以在需要的时候间接访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要更新为一个新数（即从相应归并段中读取下一个记录来替换此叶子节点中数值，或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树，从更新的叶子节点往上，依次与内部节点比较，将“败者”更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的“败者”虽然称为“败者”，但却是其所在子树中最小的数。也就是说，只要与 “败者”比较得到的胜者，就是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。 注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。 总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较“一次”即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，“有可能”会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比 堆少一倍，但是走的层数堆可能会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。 具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是 O（Nlogn）。 前面有提到，堆的优点中包括“完全树”，“用数组实现”，以及“父节点与左右子节点之间的下标的特殊关系”。其实败者树也可以用数组来实现。原理和堆的数组实现是相同的，唯一的区别是堆的所有节点都是数据节点，而败者树只有叶子节点是数据节点。所以在空间复杂度上，败者树所需的空间大小是堆的一倍（完全树的内部节点的个数是叶子节点个数减一）。 类快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一个“轴”节点，将数列交换变成两部分，一部分全都小于等于“轴”，另一部分全都大于等于“轴”，然后对两部分 递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的“较大”那一部分的数的个数j正好是n，不也就完成了在 N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果j>n，则最大的n个数肯定在这j个数中，则问题变成在这j 个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。 令人愉悦的是，这个算法的平均复杂度是O（N）的。怎么样？比堆的O（Nlogn）可能会好一些吧？！（n如果比较大肯定会好） 需要注意的是，这里的时间复杂度是平均意义上的，在最坏情况下，每次分割都分割成1：N-2，这种情况下的时间复杂度为O（n）。但是我们还有杀手锏， 可以有一个在最坏情况下时间复杂度为O（N）的算法，这个算法是在分割数列的时候保证会按照比较均匀的比例分割，at least 3n/10-6。具体细节我就不再说了，感兴趣的人参考算法导论（Introduction to Algorithms 第二版第九章 “Medians and Orders Statistics”）。 本文快要结束了，但是还有一个问题：如果N非常大，存放在磁盘上，不能一次装载进内存呢？怎么办？对于介绍的Naive方法，堆，败者树等等，依然适用，需要注意的就是每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。而对于类快速排序方法，稍微要麻烦一些：分批读入，假设是M个数，然后从这M个数中选出n个最大的数缓存起来，直到所有的N个数都分批处理完之后，再将各批次缓存的n个数合并起来再进行一次类快速排序得到最终的n个最大的数就可以了。在运行过程中，如果缓存数太多，可以不断地将多个缓存合并，保留这些缓存中最大的n个数即可。由于类快速排序的时间复杂度是O（N），这样分批处理再合并的办法，依然有极大的可能会比堆和败者树更优。当然，在空间上会占用较多的内存。 总结：对于这个问 题，我想了很多，但是觉得还有一些地方可以继续深挖： 1. 堆和败者树到底哪一个更优？可以通过理论分析，也可以通过实验来比较。也许会有人觉得这个很无聊； 2. 有没有近似的算法或者概率算法来解决这个问题？我对这方面实在不熟悉，如果有人有想法的话可以一块交流。如果有分析错误或遗漏的地方，请告知，我不怕丢人，呵呵！最后请时刻谨记，时间复杂度不等于实际的运行时间，一个常数因子很大的O（logN）算法也许会比常数因子小的O（N）算法慢很多。所以说，n 和N的具体值，以及编程实现的质量，都会影响到实际效率。我看过一篇论文，给出的算法在进行字符串查找时，比hash还要快，是不是难以想象？ -----1,fread是带缓冲的,read不带缓冲. 2,fopen是标准c里定义的,open是POSIX中定义的. 3,fread可以读一个结构.read在linux/unix中读二进制与普通文件没有区别. 4,fopen不能指定要创建文件的权限.open可以指定权限. 5,fopen返回指针,open返回文件描述符(整数). 6,linux/unix中任何设备都是文件,都可以用open,read. 如果文件的大小是8k。 你如果用read/write，且只分配了2k的缓存，则要将此文件读出需要做4次系统调用来实际从磁盘上读出。 如果你用fread/fwrite，则系统自动分配缓存，则读出此文件只要一次系统调用从磁盘上读出。 也就是用read/write要读4次磁盘，而用fread/fwrite则只要读1次磁盘。效率比read/write要高4倍。 如果程序对内存有限制，则用read/write比较好。 都用fread 和fwrite,它自动分配缓存,速度会很快,比自己来做要简单。如果要处理一些特殊的描述符,用read 和write,如套接口,管道之类的 系统调用write的效率取决于你buf的大小和你要写入的总数量，如果buf太小，你进入内核空间的次数大增，效率就低下。而fwrite会替你做缓存，减少了实际出现的系统调用，所以效率比较高。 如果只调用一次(可能吗?)，这俩差不多，严格来说write要快一点点(因为实际上fwrite最后还是用了write做真正的写入文件系统工作)，但是这其中的差别无所谓。换一张
上一页 1 ... -1 -1 -1 -1 -1 -1 -1 ... -1 下一页
换一张