Python一行代码实现快速排序的方法

今天将单独为大家介绍一下快速排序!

一、算法介绍

排序算法(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一行代码实现快速排序的方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • python实现快速排序的示例(二分法思想)

    本文介绍了python实现快速排序的示例(二分法思想),分享给大家,具体如下: 实现思路 将所需要的数字存入一个列表中 1.首先,设置将最左侧的那个数设置为基准数,在列表中索引为0 2.然后设置两个移动位(用于比较),分别为最左边和最右边 3.然后最右边那位向左移寻找比基准数小的那一位,最右边那位则从左向右寻找比基准数大的那一位 4.再后,将找到的两位对应的数字替换,继续执行3,直到两个移动位相遇,把基准为替换到相遇的那一位 5.最后,将列表以基准数那一位一分为二切开,左边和右边部分继续执行上述

  • 快速排序的算法思想及Python版快速排序的实现示例

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 1.分治法的基本思想 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题.递归地解这些子问题,然后将这些子问题的解组合为原问题的解. 2.快速排序的基本思想 设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为: (1)分解: 在R[low..high]中任选一个记录作为基准(

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例

    本文实例讲述了Python实现的插入排序,冒泡排序,快速排序,选择排序算法.分享给大家供大家参考,具体如下: #!/usr/bin/python # coding:utf-8 #直接插入排序 def insert_sort(list): for i in range(len(list)): Key = list [i] #待插入元素 j = i - 1 while(Key < list[j] and j >= 0): list[j+1] = list[j] #后移元素 list[j] = Ke

  • Python实现快速排序算法及去重的快速排序的简单示例

    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用. 该方法的基本思想是: 1.先从数列中取出一个数作为基准数. 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3.再对左右区间重复第二步,直到各区间只有一个数. 现在通过一个实例来说明快排. 比如有一个数组: 6 2 4 5 3 第一步:选取一个基准数,不要被这个名词吓到了,你可以把它看作是一个比较大小的数,因为排序就是比较大小, 比如我选取最后一个数3为基准数,依次把数组的数和

  • python 二分查找和快速排序实例详解

    思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e

  • Python实现快速排序的方法详解

    本文实例讲述了Python实现快速排序的方法.分享给大家供大家参考,具体如下: 说起快排的Python实现,首先谈一下,快速排序的思路: 1.取一个参考值放到列表中间,初次排序后,让左侧的值都比他小,右侧的值,都比他大. 2.分别对左侧和右侧的部分递归第1步的操作 实现思路: 两个指针left,right分别指向列表的第一个元素和最后一个元素,然后取一个参考值,默认为第一个列表的第一个元素list[0],称为K 然后left指向的值先和参考值K进行比较,若list[left]小于或等于K值,le

  • Python编程二分法实现冒泡算法+快速排序代码示例

    本文分享的实例主要是Python编程二分法实现冒泡算法+快速排序,具体如下. 冒泡算法: #-*- coding: UTF-8 -*- #冒泡排序 def func(lt): if type(lt).__name__ !='list' and type(lt).__name__ !='tuple': return if type(lt).__name__ == 'tuple': return list(lt) for i in range(1,len(lt)-1): for j in range

  • python快速排序代码实例

    一. 算法描述: 1.先从数列中取出一个数作为基准数.2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边.3.再对左右区间重复第二步,直到各区间只有一个数.  二.python快速排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def sub_sort(array,low,high):    key = array[low]    while low < high:        while low <

  • Python实现快速排序和插入排序算法及自定义排序的示例

    一.快速排序 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 快速排序,递归实现 def quick_sort(num_list): """ 快速排序 """ if num_li

  • 快速排序的四种python实现(推荐)

    快速排序算法,简称快排,是最实用的排序算法,没有之一,各大语言标准库的排序函数也基本都是基于快排实现的. 本文用python语言介绍四种不同的快排实现. 1. 一行代码实现的简洁版本 quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for ite

  • javascript与Python快速排序实例对比

    本文实例对比了javascript与Python快速排序实现方法.分享给大家供大家参考.具体如下: js实现方法: function quicksort(arr) { if (arr.length <= 1) return arr return quicksort(arr.filter(function (lt, i) {return i > 0 && lt < arr[0]})) .concat([arr[0]]) .concat(quicksort(arr.filte

随机推荐