数据量极大时用什么排序方法比较好

r囧r小猫 2022-05-26 07:30 200阅读 0赞

1.普遍认为：  
当N很小时，快速排序慢，归并排序快   
当N很大时，并且有序程度高时，快速排序最快   
当N很大时，并且有序程序低时，堆排序最快

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

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

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

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

//堆排序

**\[cpp\]** [view plain][] [copy][view plain]

1.  void BuildMaxHeap(int \*,int );  
2.  void MaxHeapify(int \*,int,int);  
3.  void heap\_sort(int \*,int ,int );

**\[cpp\]** [view plain][] [copy][view plain]

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.  \}

//测试堆排序

**\[cpp\]** [view plain][] [copy][view plain]

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;

**\[cpp\]** [view plain][] [copy][view plain]

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. \}

**\[cpp\]** [view plain][] [copy][view plain]

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.  \}

**\[cpp\]** [view plain][] [copy][view plain]

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.同时也指明了快速排序递归调用次数太多时会出现栈溢出，并给出了非递归版的快速排序法。

//快速排序

**\[cpp\]** [view plain][] [copy][view plain]

1.  int partition(int \*, int ,int );  
2.  void quick\_sort(int \*, int ,int);  
3.  void quick\_sort\_rec(int \*, int ,int);

//测试快速排序

**\[cpp\]** [view plain][] [copy][view plain]

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;

**\[cpp\]** [view plain][] [copy][view plain]

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. \}

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

**\[cpp\]** [view plain][] [copy][view plain]

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. \}

//非递归版 --迭代

**\[cpp\]** [view plain][] [copy][view plain]

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条进行排序找到 重复率最高的十条即可；

[view plain]: https://blog.csdn.net/gll028/article/details/8797513#

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关小程序后端用什么开发比较好

在小程序后端开发中，可以使用 Node.js 和一些框架进行开发。常见的框架有 Koa、Express、egg、Nest 等。这些框架都可以帮助开发者快速构建小程序后端服务。

蔚落/ 2024年03月26日 09:24/ 0 赞/ 110 阅读

相关什么是IDE？新手用哪个IDE比较好？

IDE(Integrated Development Environment)，全称是集成开发环境，是用于提供程序开发环境的应用程序，一般包括代码编辑器、编译器、调试器和图形

忘是亡心i/ 2023年10月07日 19:23/ 0 赞/ 50 阅读

相关什么类型用equals()比较，什么类型用==比较

在 java 中进行比较，我们需要根据比较的类型来选择合适的比较方式： 1. 对象：使用 equals。 2. 枚举：使用 equals 或== 。 3. 可能为 nu

妖狐艹你老母/ 2022年12月29日 09:09/ 0 赞/ 193 阅读

相关有哪些比较好用的代码量统计工具？

[https://www.zhihu.com/question/22004842][https_www.zhihu.com_question_22004842] 暂时选第一个

冷不防/ 2022年12月09日 02:43/ 0 赞/ 176 阅读

相关 MySQL存ip地址，用什么数据类型比较好

叙述在看高性能MySQL第3版（4.1.7节）时，作者建议当存储IPv4地址时，应该使用32位的无符号整数（UNSIGNED INT）来存储IP地址，而不是使用字符串。

喜欢ヅ旅行/ 2022年09月10日 05:07/ 0 赞/ 179 阅读

相关面试官：如果要存 IP 地址，用什么数据类型比较好？

在看高性能MySQL第3版（4.1.7节）时，作者建议当存储IPv4地址时，应该使用32位的无符号整数（UNSIGNED INT）来存储IP地址，而不是使用字符串。但是没有给

╰半橙微兮°/ 2022年09月10日 04:21/ 0 赞/ 131 阅读

相关面试官：如果要存ip地址，用什么数据类型比较好

![0D5F937FE12312312D81F17F.jpg][] 程序员的成长之路互联网/程序员/技术/资料共享 [关注][Link 1] 阅读本文大概需要 2.

太过爱你忘了你带给我的痛/ 2022年09月04日 03:58/ 0 赞/ 149 阅读

相关比较好用的java导出大数据量Excel

转载于:[http://blog.csdn.net/u010003835/article/details/51590101][http_blog.csdn.net_u01000

朴灿烈づ我的快乐病毒、/ 2022年06月13日 12:45/ 0 赞/ 255 阅读

相关比较好用的java导出大数据量Excel

转载于:[http://blog.csdn.net/u010003835/article/details/51590101][http_blog.csdn.net_u01000

绝地灬酷狼/ 2022年06月10日 14:18/ 0 赞/ 237 阅读

相关数据量极大时用什么排序方法比较好

1.普遍认为：当N很小时，快速排序慢，归并排序快当N很大时，并且有序程度高时，快速排序最快当N很大时，并且有序程序低时，堆排序最快快速排序是

r囧r小猫/ 2022年05月26日 07:30/ 0 赞/ 201 阅读