周五的下午面试了一位来自华为的高手,此高手称精通排序算法。我一听说某人精通某项,就忍不住兴奋,喜欢抓住别人最精通的这一项追根究底。一方面来说,问你最精通的东西,不能算考官故意刁难你;另一方面来说,面试别人往往成为自己变相请教高手的途径。
问之:相对于《数据结构》课本上提供的快速排序算法,有没有可以优化的余地?
本来我的原意是想听到他说将递归算法修改为非递归算法,可是聊了一些方面也没提高这个。虽然对这个问题的答案有些失望,总的来说这个高手思维积极、善于思考,仍是非常不错的。
面试完成后,我到网上查了查快速排序的一些资料,发现快速排序算法可优化的地方很多,其实我自己也是半桶水。
快速排序的优化方法包括:
1、将递归算法修改为非递归算法;
2、需要排序的元素个数如果少于8个,则使用插入排序代替快速排序;
3、使用仿函数(函数对象),而不是函数指针:模版库会将比较函数展开,从而避免函数调用带来的开销;
4、使用多线程:快速排序是分而治之的思想,每个独立的段可以并行进行排序。因此可以利用计算机的并行处理能力来提高排序的性能;
我所找到的一些参考文章如下:
·深入分析qsort库函数: http://www.programfan.com/blog/blog.asp?blogid=2592
·双核CPU上的快速排序效率:http://blog.csdn.net/drzhouweiming/archive/2006/08/23/1109499.aspx
抛砖引玉,欢迎朋友提出更多算法优化的思路,谢谢!
分享到:
相关推荐
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
快速排序算法C语言实现,快排序算法QuickSort.cpp
快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例)
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
详细解释了快速排序的java实现.里面有代码,还有注释说明
快速排序算法c++实现,快速实现插入排序十万个数(调用)。可以改成输入。并附加了程序运行计时,用于测试时间复杂度,可以移除。绝对能用
c语言版本的数据结构的快速排序算法,适用于新手学习
现在有 1 亿的数据,请选择合适的排序算法与数据结构,在有限的时间内完成进行排序。 选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大...
C++快速排序算法程序,用于处理大量数据, 并对这些数据进行快速的排序
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
快速排序算法 word格式 较快速度 MATLAB格式
快速排序算法的编码和优化 快速排序的基本思路是: 1. 先通过第一趟排序,将数组原地划分为两部分,其中一部分的所有数据都小于另一部分的所有数据。原数组 被划分为2份 2. 通过递归的处理, 再对原数组分割的两...
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
自己写的用C++实现的快速排序算法,运行通过,可以作为参考。
Java语言的快速排序优化算法实现 算法思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程...
自己编写的基于java的快速排序和归并算法
1)不做随机化处理的递归实现; 2)采用随机化处理的递归实现; 3)用while循环消除尾递归; 4)用栈模拟递归,并证明所需的栈空间为O(logn); 5) 够小时改用插入排序
快速排序算法的改进思路 1.选取好的基准,是两边的数据个数尽量的均匀 取数组的第一个,中间,最后一个数据,取三个数中第二大的数作为基准 2. 不递归 3.与插入结合,当段内的数组个数小于等于16的时候,使用...
经测试的C++快速排序算法,可直接运行 源代码