1.普遍认为：
当N很小时，快速排序慢，归并排序快 
 

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

 当N很大时，并且有序程序低时，堆排序最快


 



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



 



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


 



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



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



 //堆排序



 
 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
void BuildMaxHeap(int *,int );  
void MaxHeapify(int *,int,int);  
void heap_sort(int *,int ,int );  
 
 

 



 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
void swap(int *a, int m,int n)  
{  
    int temp=a[m];  
    a[m]=a[n];  
    a[n]=temp;  
}  
 
 

 



 //测试堆排序
 
 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
for( i=0; i<size; i++)  
 {  
     array0[i]=array_b[i];  
 }     
 i=heap_sort(array0,0,size-1);     
 cout<<"Heap Sort Running Time:"<<i<<endl;  
 fout<<"Heap Sort Running Time:"<<i<<endl;  
 
 



 



 
 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
void heap_sort(int *a,int start,int end)  
{  
    int i;  
    int length=end-start;  
    int hsize=length;  
    BuildMaxHeap(a,hsize);  
    for( i=length; i>1; i--)  
    {  
        swap(a,1,i);  
        hsize--;  
        MaxHeapify(a,1,hsize);  
    }  
  
}  
 
 

 



 
 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
void BuildMaxHeap(int *a,int size)  
{  
    int i;  
    for( i=size/2; i>0; i--)  
    {  
        MaxHeapify(a,i,size);  
    }  
}  
 
 

 



 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
void MaxHeapify(int *a,int i,int size)  
{  
    int l,r,largest;  
    l=2*i;  
    r=2*i+1;  
    if(l<=size &&a[l]>a[i])  
        largest=l;  
    else  
        largest=i;  
    if(r<=size && a[r]>a[largest])  
        largest=r;  
    if(largest!= i)  
    {  
        swap(a,i,largest);  
        MaxHeapify(a,largest,size);  
    }  
}  
 
 

 



 



 3.同时也指明了快速排序递归调用次数太多时会出现栈溢出，并给出了非递归版的快速排序法。


 //快速排序

 

  

   

    [cpp] 
    view plain
     copy
     
   
  
  
int partition(int *, int ,int );  
void quick_sort(int *, int ,int);  
void quick_sort_rec(int *, int ,int);  
 
 

  
     //测试快速排序


 

    
  

   

    

     [cpp] 
     view plain
      copy
      
    
   
   
for( i=0; i<size; i++)  
  {  
      array0[i]=array_b[i];  
  }     
  i=run_sort(quick_sort_rec,array0,0,size-1);     
  cout<<"Quick Sort Running Time:"<<i<<endl;  
  fout<<"Quick Sort Running Time:"<<i<<endl;  
  
 
 

  

 
 

  

 
 

  
  

   

    

     [cpp] 
     view plain
      copy
      
    
   
   
int partition(int *a,int low,int high)  
{  
    int i,j;      
    int key=a[high];  
    i=low-1;  
    j=low;  
    for( ; j<high; j++)  
    {  
        if(a[j]<=key)  
        {  
            i++;  
            swap(a,i,j);  
        }  
    }  
    swap(a,i+1,high);  
    return i+1;  
}  
  
  

     
 

//递归调用次数太多 栈溢出！


 

  

   [cpp] 
   view plain
    copy
    
  
 
 
void quick_sort_rec(int *a,int low,int high)  
{  
    int mid;  
    if(low<high)  
    {  
      mid=partition(a,low,high);  
    quick_sort_rec(a,low,mid-1);  
    quick_sort_rec(a,mid+1,high);  
    }  
}  





//非递归版 --迭代



 

  

   [cpp] 
   view plain
    copy
    
  
 
 
void quick_sort(int *base,int start,int end)  
{  
    const int stacksize=1000;  
    int *stack=new int[stacksize];  
    int top=0;  
    stack[top++]=start;  
    stack[top++]=end-start+1;  
    while(top!=0)  
    {  
        //cout<<top<<endl;  
        top--;  
        int r=stack[top];  
        top--;  
        int p=stack[top];         
        if(p>=r)  
            continue;  
        int m=partition(base,p,r);  
        //push the left  
        stack[top++]=p;  
        stack[top++]=m-1;  
        //push the right  
        stack[top++]=m+1;  
        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条进行排序找到 重复率最高的十条即可；

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

      【尊重
  原创，转载请注明出处
  】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很大时，并且有序程度低时，堆排序最快（当N很大时，并且有序程度高时，快速排序最快 ）。
 
另外，常见的排序算法都是使用内存的内部排序，其中，插入排序有：直接插入排序和希尔排序，选择排序有：简单选择排序(直接选择排序)和堆排序，交换排序有：冒泡排序和快速排序。
 

堆排序和快速排序的比较
 
堆排序是接近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
 
这两篇待学习