怎么制作一个属于自己的网站,西安论坛,手机兼职平台app排行榜前十名,新浪wordpress今天将单独为大家介绍一下快速排序#xff01;
一、算法介绍
排序算法#xff08;Sorting algorithm#xff09;是计算机科学最古老、最基本的课题之一。要想成为合格的程序员#xff0c;就必须理解和掌握各种排序算法。其中快速排序#xff08;Quicksort
一、算法介绍
排序算法Sorting algorithm是计算机科学最古老、最基本的课题之一。要想成为合格的程序员就必须理解和掌握各种排序算法。其中快速排序Quicksort使用得最广泛速度也较快。它是图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的。二、算法原理
快排的实现方式多种多样猪哥给大家写一种容易理解的分治迭代只需要三步
在数列之中选择一个元素作为基准pivot或者叫比较值。数列中所有元素都和这个基准值进行比较如果比基准值小就移到基准值的左边如果比基准值大就移到基准值的右边以基准值左右两边的子列作为新数列不断重复第一步和第二步直到所有子集只剩下一个元素为止。
举个例子假设我现在有一个数列需要使用快排来排序{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}我们来看看使用快排的详细步骤
选取中间的26作为基准值基准值可以随便选数列从第一个元素3开始和基准值26进行比较小于基准值那么将它放入左边的分区中第二个元素44比基准值26大把它放入右边的分区中依次类推就得到下图中的第二列。然后依次对左右两个分区进行再分区得到下图中的第三列依次往下直到最后只有一个元素分解完成再一层一层返回返回规则是左边分区基准值右边分区三、代码实现
是不是很简洁很秀如果再有面试官让你手写一个快排你就把这行写上去吧面试官见了都要喊你秀儿哈哈。
在你感叹python吊炸天的同时你因该考虑到代码的可读性问题lambda函数设计是为了代码的简洁性但是滥用的话会导致可读性变得极差而且现在pep8代码规范中也不建议使用lambda函数了建议使用关键字def去定义一个函数所以下面猪哥给大家写一段符合pythonic风格的快排代码
四、算法分析稳定性
快排是一种不稳定排序比如基准值的前后都存在与基准值相同的元素那么相同值就会被放在一边这样就打乱了之前的相对顺序比较性因为排序时元素之间需要比较所以是比较排序时间复杂度快排的时间复杂度为O(nlogn)空间复杂度排序时需要另外申请空间并且随着数列规模增大而增大其复杂度为O(nlogn)归并排序与快排 归并排序与快排两种排序思想都是分而治之但是它们分解和合并的策略不一样归并是从中间直接将数列分成两个而快排是比较后将小的放左边大的放右边所以在合并的时候归并排序还是需要将两个数列重新再次排序而快排则是直接合并不再需要排序所以快排比归并排序更高效一些可以从示意图中比较二者之间的区别。五、快排优化
快速排序有一个缺点就是对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术最终来说大的数据集都要分为小的数据集来进行处理所以快排分解到最后几层性能不是很好所以我们就可以使用扬长避短的策略去优化快排
先使用快排对数据集进行排序此时的数据集已经达到了基本有序的状态然后当分区的规模达到一定小时便停止快速排序算法而是改用插入排序因为我们之前讲过插入排序在对基本有序的数据集排序有着接近线性的复杂度性能比较好。
这一改进被证明比持续使用快速排序算法要有效的多。
六、模拟面试面试官
你了解快排吗你略知一二面试官那你讲讲快排的算法思想吧你快排基本思想是从数据集中选取一个基准然后让数据集的每个元素和基准值比较小于基准值的元素放入左边分区大于基准值的元素放入右边分区最后以左右两边分区为新的数据集进行递归分区直到只剩一个元素。面试官快排有什么优点有什么缺点你分治思想的排序在处理大数据集量时效果比较好小数据集性能差些。面试官那该如何优化你对大规模数据集进行快排当分区的规模达到一定小时改用插入排序插入排序在小数据规模时排序性能较好。面试官那你能手写一个快排吗你
七、总结
以上所述是小编给大家介绍的Python一行代码实现快速排序的方法,希望对大家有所帮助如果大家有任何疑问请给我留言小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持
如果你觉得本文对你有帮助欢迎转载烦请注明出处谢谢
