精华内容
下载资源
问答
  • 1.普遍认为:当N很小时,快速排序慢,归并排序快 当N很大时,并且有序程度高时,快速排序最快 当N很大时,并且有序程序低时,堆排序最快快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字...
    1.普遍认为:
    当N很小时,快速排序慢,归并排序快 

    当N很大时,并且有序程度高时,快速排序最快 
    当N很大时,并且有序程序低时,堆排序最快

    快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
    堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    若要求排序稳定,则可选用归并排序。先利用直接插入排序求得较长的有序子文件,然后再两两归并之。因为直接插入排序是稳定的,所以改进后的归并排序仍是稳定的。

    但是:由于快速排序不稳定,因此数据量极大时不如选用堆排序。

    2.  堆排序占花费是时间主要是在建堆的时候。
    所以在数据量方面来说,如果数据量越大,堆排序的优势就越明显。

    大多数商用软件都采用快排,因为它在一般情况下是排序最快的算法。
    然而,快排绝不能用于需要特定响应时间的系统,除非这个系统能承受O(n^2)的时间复杂度。
    如果你预先估计可能会碰到这种最坏情况,那么
    如果n比较小,改用插入排序——由于代码简单,它的时间复杂度的常数项比较少
    如果n比较大,改用堆排序——你应该用堆排序,因为它能保证O(nlogn)的时间复杂度.
    //堆排序
    1. void BuildMaxHeap(int *,int );  
    2. void MaxHeapify(int *,int,int);  
    3. void heap_sort(int *,int ,int );  


    1. void swap(int *a, int m,int n)  
    2. {  
    3.     int temp=a[m];  
    4.     a[m]=a[n];  
    5.     a[n]=temp;  
    6. }  


    //测试堆排序
     
    1. for( i=0; i<size; i++)  
    2.  {  
    3.      array0[i]=array_b[i];  
    4.  }     
    5.  i=heap_sort(array0,0,size-1);     
    6.  cout<<"Heap Sort Running Time:"<<i<<endl;  
    7.  fout<<"Heap Sort Running Time:"<<i<<endl;  


    1. void heap_sort(int *a,int start,int end)  
    2. {  
    3.     int i;  
    4.     int length=end-start;  
    5.     int hsize=length;  
    6.     BuildMaxHeap(a,hsize);  
    7.     for( i=length; i>1; i--)  
    8.     {  
    9.         swap(a,1,i);  
    10.         hsize--;  
    11.         MaxHeapify(a,1,hsize);  
    12.     }  
    13.   
    14. }  


    1. void BuildMaxHeap(int *a,int size)  
    2. {  
    3.     int i;  
    4.     for( i=size/2; i>0; i--)  
    5.     {  
    6.         MaxHeapify(a,i,size);  
    7.     }  
    8. }  


    1. void MaxHeapify(int *a,int i,int size)  
    2. {  
    3.     int l,r,largest;  
    4.     l=2*i;  
    5.     r=2*i+1;  
    6.     if(l<=size &&a[l]>a[i])  
    7.         largest=l;  
    8.     else  
    9.         largest=i;  
    10.     if(r<=size && a[r]>a[largest])  
    11.         largest=r;  
    12.     if(largest!= i)  
    13.     {  
    14.         swap(a,i,largest);  
    15.         MaxHeapify(a,largest,size);  
    16.     }  
    17. }  



    3.同时也指明了快速排序递归调用次数太多时会出现栈溢出,并给出了非递归版的快速排序法。
    //快速排序
    1. int partition(int *, int ,int );  
    2. void quick_sort(int *, int ,int);  
    3. void quick_sort_rec(int *, int ,int);  

          //测试快速排序
      
    1. for( i=0; i<size; i++)  
    2.   {  
    3.       array0[i]=array_b[i];  
    4.   }     
    5.   i=run_sort(quick_sort_rec,array0,0,size-1);     
    6.   cout<<"Quick Sort Running Time:"<<i<<endl;  
    7.   fout<<"Quick Sort Running Time:"<<i<<endl;  


    1. int partition(int *a,int low,int high)  
    2. {  
    3.     int i,j;      
    4.     int key=a[high];  
    5.     i=low-1;  
    6.     j=low;  
    7.     for( ; j<high; j++)  
    8.     {  
    9.         if(a[j]<=key)  
    10.         {  
    11.             i++;  
    12.             swap(a,i,j);  
    13.         }  
    14.     }  
    15.     swap(a,i+1,high);  
    16.     return i+1;  
    17. }  

       
    //递归调用次数太多 栈溢出!
    1. void quick_sort_rec(int *a,int low,int high)  
    2. {  
    3.     int mid;  
    4.     if(low<high)  
    5.     {  
    6.       mid=partition(a,low,high);  
    7.     quick_sort_rec(a,low,mid-1);  
    8.     quick_sort_rec(a,mid+1,high);  
    9.     }  
    10. }  


    //非递归版 --迭代
    1. void quick_sort(int *base,int start,int end)  
    2. {  
    3.     const int stacksize=1000;  
    4.     int *stack=new int[stacksize];  
    5.     int top=0;  
    6.     stack[top++]=start;  
    7.     stack[top++]=end-start+1;  
    8.     while(top!=0)  
    9.     {  
    10.         //cout<<top<<endl;  
    11.         top--;  
    12.         int r=stack[top];  
    13.         top--;  
    14.         int p=stack[top];         
    15.         if(p>=r)  
    16.             continue;  
    17.         int m=partition(base,p,r);  
    18.         //push the left  
    19.         stack[top++]=p;  
    20.         stack[top++]=m-1;  
    21.         //push the right  
    22.         stack[top++]=m+1;  
    23.         stack[top++]=r;  }}

    附上阿里面试题:

     问题一:若有1T的数据,比如 只有两列,身份证号和姓名 需要实现由大到小排序,你用什么办法,能否做到 复杂度为O(n),说说你的思路和想法?

        问题二:有10个G的数据,也是一样,比如两列,身份证号和姓名,如果两条数据一样,则表示该两条数据重复了,现在给你512的内存,把这10G中重复次数最高的10条数据取出来。
     

    参考思路:

    用身份证号的前三位切割这个数据,这样会分成999份,

    每一份再进行排序,比如构造一个平衡二叉树,最典型的的就是TreeMap和TreeSet(TreeSet底层是使用了TreeMap算法,而TreeMap算法底层是实现了红黑树的平衡二叉树的排序);
    然后按照文件名进行排序,这样就实现了大数据排序;
    因为排序二叉树的复杂度为O(lgn)到O(n) ;
    因此我们可以做到 O(n)
     
    问题二:
     
    解法是一样的 按照身份证号前三位 分割999份,然后对这每个文件找到重复的最多的十条,这样,我们得到了999个文件,每个文件有 10条数据
     
    在对这个999*10条进行排序找到 重复率最高的十条即可;

    展开全文
  • 数据量很大排序问题 大量数据如何排序

    万次阅读 多人点赞 2016-04-14 15:33:16
    数据量很大排序问题 大量数据如何排序  【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/51119499  同学某天参加腾讯面试,技术面的时候,面试官问了排序问题:   问题一:若有...

    数据量很大的排序问题 大量数据如何排序

        【尊重 原创,转载请注明出处 】http://blog.csdn.net/guyuealian/article/details/51151674
        同学某天参加腾讯面试,技术面的时候,面试官问了排序问题:
       问题一:若有1T的数据,需要实现由大到小排序,你用什么办法,说说你的思路和想法?
       问题二:有10个G的数据,如果两条数据一样,则表示该两条数据重复了,现在给你512的内存,把这10G中重复次数最高的10条数据取出来。
       分析:问题一和问题二思路基本是一样的,对于这种题目,利用常规的排序方法(如插入排序,快速排序……),自然是不能解决问题的!因此数据量太大。注意内部排序和外部排序的区别
       排序算法分为内部排序和外部排序:
        (1)内部排序:
    指的是待排序记录存放在计算机随机存储器(内存)中进行的排序过程;我们熟悉常用的冒泡排序,选择排序,插入排序,快速排序,堆排序,归并排序,希尔排序……等都属于内部排序方法;
         内部排序算法的比较:



        (2)外部排序:指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中需要对外存进行访问的排序过程;
          基本思路:外部排序指的是大文件的排序,即待排序的记录存储在外部存储器上,在排序过程中需进行多次的内、外存之间的交换。首先将打文件记录分成若干个子文件,然后读入内存中,并利用内部排序的方法进行排序;然后把排序好的有序子文件(称为:归并段)重新写入外存,再对这些归并段进行逐个归并,直到整个有序文件为止。
         例子:假设有10 000个记录的文件需要排序,则先把这10 000个记录文件分成10个归并段(R1…~R10,每段1000个记录),然后逐个读入归并段进行内部排序(共10次),然后把排序好的归并段重新写入外存中,再进行两两归并,直到得到一个有序文件为止。

    先来看看各位大神对问题解答:http://bbs.csdn.net/topics/390360278?page=1
    思路一:
    【1】先排序, 10G数据分成40份,每份256M,排序,合并相同数据并加上计数器,写到临时文件chunk01~chunk20。
    【2】对每一chunk, 读入内存,对每一条数据,再依次读入其后续个chunk, 合并相同数据的计数,后写入一个文件count。为了避免重复计数,在计数累加后需要将原来chunk的计数清零并回写文件。
     以chunk01为例。假设chunk01中有数据A-8(数据A, 8次),chunk02中有A-2,那么合并chunk02后
      chunk01的内存中为A-10, chunk02中为A-0,这时把chunk02写回文件,然后读入chunk03继续处理处理。最后把chunk01中计数不为0的数据(chunk01里不会有计数为0的,但是后面的chunk会有)写入文件count.
    【3】对count文件进行按重复次数排序。(分组,排序,然后每组选前10,再排序)
    思路二:
       对于问题二,个人觉得,分组统计,最后合并的方法是不可取的,因为有可能某个值A,在你每个分组中出现的次数都没有排进前10,但是将它在每个分组中的次数加起来,是能排进前10的。所以应该还是计数排序。
       其次是这10G数据时什么,是10G个BYTE,还是10G个字符串。因为BYTE的范围0-255,也就是说这个问题就变成了,找0-255范围内,出现次数最多的10个数,用int64[255]来计数,遍历一次,每个数值对应下标里面记录其出现的次数就可以了,用int64是因为DWORD表示不了10G。如果是字符串,或者是其他2进制数据块,就比较复杂,需要多次遍历。2进制数据块有多少个字节,就需要准备多少个int64[255]计数数组
       假定每条记录,就是每个2进制数据块长10个字节,对于不足10字节的记录,不足的部分以0计算需要的计数数组为int64[10][255],对于每条记录的第一个字节相同的,算为相同记录的情况下,得出表:
    A********* 1000次
    B********* 900次
    C********* 900次
    D********* 890次
    ...统计结果计入int64[0][255]
    然后对于100次的A*********,统计
    AE******** 50次
    AA******** 50次
    AD******** 49次
    AC******** 47次
    ...统计结果计入int64[1][255]
    依此类推
    AEDBBCADE* 10次
    AEDBBCADB* 9次
    AEDBBCADC* 9次
    AEDBBCADA* 8次
    ...统计结果计入int64[8][255]
    最终
    AEDBBCADEA 3次
    AEDBBCADEF 3次
    AEDBBCADEC 2次
    AEDBBCADEB 2次
    ...统计结果计入int64[9][255]
    将这个结果放入另一个int64[255] res,这个就是当前的最终结果
    然后逐个向前递归
    对于int64[8][255]中排行第二的“AEDBBCADB* 9次”
    统计出前10,得到一个新的int64[9][255],将其与res中的结果比较,得出这20个中的前10,更新res
    依此类推,得出最终结果
    展开全文
  • 归并排序 快速排序排序  对于内存足够大的大量数据排序,一般来说归并排序比较好的,因为他的读取次数会比较少(在数据挖掘的理论里面,读取次数越少,排序方法越...也可以利用堆排序,当N很大时,并且有序...
    1. 归并排序
    2. 快速排序
    3. 堆排序

        对于内存足够大的大量数据排序,一般来说用归并排序比较好的,因为他的读取次数会比较少(在数据挖掘的理论里面,读取次数越少,排序方法越快),同时是稳定的;但是如果内存空间不足,就自然要减少次数了,所以也可以用快速排序快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;也可以利用堆排序,当N很大时,并且有序程度低时,堆排序最快(当N很大时,并且有序程度高时,快速排序最快 )。

    另外,常见的排序算法都是使用内存的内部排序,其中,插入排序有:直接插入排序和希尔排序,选择排序有:简单选择排序(直接选择排序)和堆排序,交换排序有:冒泡排序和快速排序。

    展开全文
  • 大数据量排序算法小结

    千次阅读 2018-07-25 00:18:11
    排序和快速排序的比较 堆排序是接近nlgn的下界,而快排有性能坏的情况,为何还是快排表现更优秀呢? 1.堆排序是处理数组中相隔较远的数据,快速排序是根据两个 指针按序...在低数据量时候,性能不错;但是非...

    堆排序和快速排序的比较

    堆排序是接近nlgn的下界,而快排有性能坏的情况,为何还是快排表现更优秀呢?

    1.堆排序是处理数组中相隔较远的数据,快速排序是根据两个 指针按序遍历的,根据寄存器、高速缓存的热cache、 局部性原理,快排更好

    2.快排的极端情况太难复现,而且可以 用随机基准数

    3.快排还有各种优化的方案

     

     

    基数排序的性能

    在低数据量的时候,性能很不错;但是非常占内存。一般我们不会采取高内存换空间的算法(数据量大的时候就太恐怖了)

     

    综合性能

     

    数据多到内存装不下怎么办?

     (假设内存有100M容量)比如1G的数据,分10份,每份100M。先用快排让每一份各自排好序,然后写到文件中。这10份100M的 文件这个时候已经有序了。这10份每份取9M,一共90M,使得他们合并。合并后的结果放到10M的缓存区中,满了就clear,IO到 文件中。

     

    一百、一万、一亿选取什么算法最好?

    100可以基数、桶,这些很占内存,而且有一些限制条件,但是很快!

    10000可以快排

    一亿只能快排(因为热cache,所以比堆排序好)+归并(数据太大装不下)

     

    大部分数据有序的情况下,用什么 算法比较好?

    插入+二分。

     

    从大量数据中取出前100个

    第一反应是开始做题吗?no,大量数据,内存肯定是装不下的。那我们就假设所有数据被分成了N份吧。

    先看第一份,排序前100个,然后后面的数都插入+二分去修改前100个数。

    一份读完,就clear后面的数, 加载新的文件进来。

     这样一次遍历就解决了。

     

    https://blog.csdn.net/ztkhhhhhd/article/details/53138631

    https://blog.csdn.net/zhushuai1221/article/details/51781002

    这两篇待学习

    展开全文
  • sql数据量大排序问题

    千次阅读 2018-08-01 18:49:23
    问题:sql数据量大,内存无法满足,如何进行排序? 网上搜不到具体的答案,也不知道总结的对不对。 多帖子都提到一个外部排序,采用多路归并算法。外部排序是指将数据存储在外部磁盘而不是内存中,内存中的排序是...
  • 大数据量实时统计排序分页查询(并发数较小时) 的瓶颈不是函数(count,sum等)执行, 不是having, 也不是order by,甚至不是表join, 导致慢的原因就在于“数据量本身” 化整为零 就是将表划分为M份相互独立的...
  • es 在数据量很大的情况下(数十亿级别)如何提高查询效率啊? 面试官心理分析 这个问题是肯定要问的,说白了,就是看你有没有实际干过 es,因为啥?其实 es 性能并没有你想象中那么好的。很多时候数据量大了,特别...
  • 问题描述 百度面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记录(这些查询串的重复度比较高,...外部排序指的是文件的排序...
  • 由于《数据结构》课本中各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。所以我希望通过随机数据去比较各种算法的关键字比较次数和关键字移动次数,同时给出实际排序时间,以取得...
  • mysql 大数据量时 limit查询优化

    千次阅读 2018-03-13 18:45:39
    #返回第6-15行数据但是,如果数据量很大,比如&gt;1000万,则利用以上的查询会非常慢,可以利用以下语句进行优化:Select * From table Where ID&gt;=( Select ID From table order by ID limit 90000,1 )...
  • es 在数据量很大的情况下(数十亿级别)如何提高查询效率啊? 面试官心理分析 这个问题是肯定要问的,说白了,就是看你有没有实际干过 es,因为啥?其实 es 性能并没有你想象中那么好的。很多时候数据量大了,特别...
  • 2.数据量,如果你cdb_members的记录多,远远大于500条,可以考虑改变程序,先从此表里面获取500条数据,然后在循环里面每条数据库关联获取其它表的信息,这样就不需要先对五个表做链接。尽量不适用联合查询,...
  • 如果面试的时候碰到这样一个面试题:ES 在数据量很大的情况下(数十亿级别)如何提高查询效率? 这个问题说白了,就是看你有没有实际过 ES,因为啥?其实 ES 性能并没有你想象中那么好的。 很多时候数据量大了,...
  • 大数据量的五种处理方式

    万次阅读 2018-09-19 17:02:01
    处理海量数据问题,无非就是: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序; Bloom filter/Bitmap; Trie树/数据库/倒排索引; 外排序; 分布式处理之hadoop/mapreduce。 本文接下...
  • MySQL 面试题

    万次阅读 多人点赞 2019-09-02 16:03:33
    实际场景下,例如说商品表数据量比较的情况下,会将商品描述单独存储到一个表中。即,使用拆的方案。 MySQL 有哪些存储引擎? MySQL 提供了多种的存储引擎: InnoDB MyISAM MRG_MYISAM MEMORY CSV...
  • MySql下大数据量级别(1000万+)优化查询和操作方法 一、【原则一】:insert into tb (...) values(...),(...)...; 要比insert into tb (...) values (...);insert into tb (...) values (...);...方式批量插入...
  • 数据结构之八大排序总结

    千次阅读 多人点赞 2019-04-23 15:59:31
    1、排序的概念:排序就是将一组数据按照一定的顺序,递增或递减排列起来。 2、排序的稳定性:对于两个关键字相等的...4、八大排序:插入排序、希尔排序、选择排序、快速排序、冒泡排序、堆排序、归并排序、计数排...
  • ElasticSearch面试 - es 在数据量很大的情况下如何提高查询效率啊? 面试题 es 在数据量很大的情况下(数十亿级别)如何提高查询效率啊? 面试官心理分析 这个问题是肯定要问的,说白了,就是看你有没有实际干...
  • 数据结构之九大排序(JAVA)

    千次阅读 2017-03-05 17:08:19
    最近面临实习面试,由于自己准备投开发岗,据了解在面试中对于数据结构的考察是重要的,其中对于查找、排序的算法考察尤为重要,所以又重回当年学习的数据结构好好复习。参考:《数据结构》 严蔚敏版、《考研数据...
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    -p: 当关机的时候顺便做关闭电源的动作。 -d:关闭系统,但不留下纪录。  4.命令说明 halt 就是调用shutdown -h。halt执行时,杀死应用进程,执行sync(将存于buffer中的资料强制写入硬盘中)系统调用,文件...
  • C 数据结构之十大排序查找

    千次阅读 多人点赞 2018-11-08 19:40:28
    排序算法的稳定性: 若排序对象中存在多个关键字相同的记录,经过排序后,相同关键字的记录之间的相对次序保持不变,则该排序方法是稳定的,若次序发生变化(哪怕只有两条记录之间),则该排序方法是不稳定的。...
  • 1.合理使用索引索引是数据库中重要的数据结构,它的根本目的就是为了提高查询效率。现在大多数的数据库产品都采用IBM最先提出的ISAM索引结构。索引的使用要恰到好处,其使用原则如下:●在经常进行连接,但是没有...
  • 一亿条数据排序处理

    万次阅读 2016-05-18 23:28:37
    经测试,直接使用TreeSet来处理,一千万数据量很轻松就能处理,大概排序耗时20秒左右。 但是,一亿数据量时就废了!CPU满,内存占用上2.5G左右,并且N多分钟后不出结果,只能结束进程!(有条件的话,可以试试,...
  • 海量数据处理:排序问题

    千次阅读 2018-06-15 22:44:58
    一个文件中有9亿条不重复的9位整数,对这个文件中数字...但这些方法在此并不适用,由于数据量巨大,对32位机器而言,难将这么多数据一次载入到内存,更不用说进行排序了.所以此种方法一般不可行,需要考虑其他方法.方...
  • 大数据算法:对5亿数据进行排序

    万次阅读 多人点赞 2015-10-19 23:32:03
    在大数据研究的路上,我们总要对一些很大数据进行各种各样的操作。比如说对数据排序,比如说对数据统计,比如说对数据计算。而在大量的数据面前,我们总是束手无策,因为我们无法在限定时间的情况下,在效率上做到...
  • 大数据量的算法面试题

    万次阅读 2016-08-19 15:16:28
    何谓海量数据处理?...何谓海量,就是数据量,所以导致要么是无法在较短时间内迅速解决,要么是数据太,导致无法一次性装入内存。  那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构
  • sort按照数据大小排序

    千次阅读 2017-04-10 10:42:24
    一般默认的sort都是按照字母的ASCII进行排序的,现在想按照数字的大小进行排序这里有一个文件test,内容为:8723 23423 321324 213432 23 234 123 231 234 1234 654 345234对第一列排序sort -n test对第二列...
  • 索引

    千次阅读 多人点赞 2018-09-07 23:27:20
    索引是一种对数据库表中一列或多列的值进行排序的一种数据存储结构。 需要占用磁盘空间。 类型:普通索引,唯一索引,主键索引,复合索引,聚族索引。 唯一索引:不允许具有索引值相同的行,即每一行数据的索引的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 498,380
精华内容 199,352
关键字:

数据量很大的时候用什么排序