精华内容
下载资源
问答
  • Python 快速排序

    万次阅读 2019-11-27 20:12:43
    Python 快速排序 基本原理: 利用递归的思想,在开始的时候选择一个基准值,大于这个基准值的数存放到一个列表中,其他值存放到另一个列表中,然后这两个列表进行递归操作。 时间复杂度为O(nlog2n),n为数组的个数。...

    Python 快速排序

    基本原理:

    利用递归的思想,在开始的时候选择一个基准值,大于这个基准值的数存放到一个列表中,其他值存放到另一个列表中,然后这两个列表进行递归操作。

    时间复杂度为O(nlog2n),n为数组的个数。

    空间复杂度为O(nlog2n)。

    不稳定算法。
    快速排序算法
    该图片来源于网络

    快速排序

    def quick_sort(array):
        """
        快速排序
    
        :param array: 数组
        :return: (array)已排序的数组
        """
        # 递归退出的条件
        length = len(array)
        if length <= 1:
            return array
        else:
            # 可以选第一个元素作为基准值,也可以选最后一个
            pivot = array.pop()
            greater, lesser = [], []
            for element in array:
                if element > pivot:
                    greater.append(element)
                else:
                    lesser.append(element)
            return quick_sort(lesser) + [pivot] + quick_sort(greater)
    展开全文
  • Python快速排序

    2019-08-21 20:57:12
    Python快速排序 思想: 每次选择一个数字,固定该数字的正确排序位置,即使得该数字左边的值全小于它,右边的值全大于它 该数字的左序列和右序列递归执行上一步 def quick_sort(alist, start, end): '''...

    Python快速排序

    在这里插入图片描述

    思想

    1. 每次选择一个数字,固定该数字的正确排序位置,即使得该数字左边的值全小于它,右边的值全大于它
    2. 该数字的左序列和右序列递归执行上一步
    def quick_sort(alist, start, end):
        '''快速排序'''
        if start >= end:      
            return
    
        mid_value = alist[start]     # 将序列第一个值设为比较值(中间值)
        low, high= start, end
    
        while low < high:                                   # 序列两端指针遍历,直至相遇
            
            while low < high and alist[high] >= mid_value:  # 从后往前找比中间值小的数字
                high -= 1
            alist[low] = alist[high]                        # 将该数字放置 low 位置
    
            while low < high and alist[low] < mid_value:    # 从前往后找比中间值大或相等的数字
                low += 1 
            alist[high] = alist[low]                        # 将该数字放置 high 位置
            
        alist[low] = mid_value                              # 此时序列 low 位置左边全为比中间值小的值,右边全为比中间值大的值,low 位置即为该数字排序后的正确位置
    
        quick_sort(alist, start, low-1)   # 递归左序列
        quick_sort(alist, low+1, end)     # 递归右序列
    
    alist = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    quick_sort(alist, 0, len(alist)-1)
    print(alist)
    
    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    

    总结

    最优时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性
    O(nlogn)O(nlogn) O(n2)O(n^2) O(nlogn)O(nlogn) O(nlogn)O(nlogn) 不稳定

    图片来源于:菜鸟教程

    展开全文
  • python快速排序

    千次阅读 2019-04-01 19:17:49
    快速排序,⼜称划分交换排序 1.通过⼀趟排序将要排序的数据分割成独⽴的两部分, 其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩ 2.然后再按此⽅法对这两部分数据分别进⾏快速排序,整个排序过程可以递归进⾏...

    快速排序,⼜称划分交换排序

    1.通过⼀趟排序将要排序的数据分割成独⽴的两部分,
    其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩
    2.然后再按此⽅法对这两部分数据分别进⾏快速排序,整个排序过程可以递归进⾏,以此达到整个数据变成有序序列。

    步骤为:

    1. 从数列中挑出⼀个元素,称为"基准"(pivot)
    2. 重新排序数列,所有元素⽐基准值⼩的摆放在基准前⾯,所有元素⽐基准值⼤的摆在基准的后⾯(相同的数可以到任⼀边)。
    3. 在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    4. 递归地(recursive)把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦
      数列排序。

    递归的最底部情形,是数列的⼤⼩是零或⼀,也就是永远都已经被排序好了。虽然⼀直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它⾄少会把⼀个元素摆到它最后的位置去。

    def quick_sort(list1, start, end):
        # 递归的退出条件
        if start >= end:
            return
        # 设置起始元素为要寻找位置的基准元素
        mid = list1[start]
        # left为序列左边的由左向右移动的游标
        left = start
        # right为序列右边的由右向左移动的游标
        right = end
        while left < right:
            # 如果left和right未重合,right指向的元素不比基准元素小,
            # 则right向左移动
            while left < right and list1[right] >= mid:
                right -= 1
            # 将right指向的元素放到left的位置上
            list1[left] = list1[right]
            # 如果left于right未重合,left指向的元素比基准元素小
            # 则left向右移动
            while left < right and list1[left] < mid:
                left += 1
            # 将left指向的元素放到right的位置上
            list1[right] = list1[left]
    
        # 退出循环后,left与right重合,此时所指位置为基准元素的正确位置
        # 将基准元素放到该位置
        list1[left] = mid
        # 对基准元素左边的子序列进行快速排序
        quick_sort(list1, start, left-1)
        # 对基准元素右边的子序列进行快速排序
        quick_sort(list1, left+1, end)
    
    
    li = [23, 94, 2, 21, 56, 6]
    quick_sort(li, 0, len(li)-1)
    print(li)
    
    
    展开全文
  • 主要介绍了Python快速排序算法,简单说明了快速排序算法的原理、实现步骤,并结合具体实例分析了Python实现快速排序的相关操作技巧,需要的朋友可以参考下
  • 主要介绍了javascript与Python快速排序实例对比,实例讲述了javascript与Python实现快速排序的简单实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • python 快速排序

    千次阅读 2015-08-07 21:39:26
    某公司的面试题之一。 python写一个快排。

    某公司的面试题之一。

    RT。

    def exchange(mylist,i,j):
        tmp = mylist[i]
        mylist[i] = mylist[j]
        mylist[j] = tmp
    
    def patition(mylist,p,q):
        key = mylist[q]
        i = p-1
        for j in range(p,q):
            if mylist[j] <= key:
                i = i+1
                exchange(mylist,i,j)
        exchange(mylist,i+1,q)
        return i
        
    def quicksort(mylist,p,q):
        if p < q:
            r = patition(mylist,p,q)
            quicksort(mylist,p,r-1)
            quicksort(mylist,r+1,q)
        
    mylist = [5,8,0,2,1,9,10,3,6,7,4]
    quicksort(mylist,0,len(mylist)-1)
    print mylist
          

    结果:

    >>> 
    [0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10]
    >>> 


    改进版本,因为pyhon交换a,b = b,a 即可。

    def patition(mylist,p,q):
        key = mylist[q]
        i = p-1
        for j in range(p,q):
            if mylist[j] <= key:
                i = i+1
                mylist[i],mylist[j] = mylist[j], mylist[i]
        mylist[i+1],mylist[q] = mylist[q], mylist[i+1]
        return i
        
    def quicksort(mylist,p,q):
        if p < q:
            r = patition(mylist,p,q)
            quicksort(mylist,p,r-1)
            quicksort(mylist,r+1,q)
        
    mylist = [5,8,0,2,1,9,10,3,6,7,4]
    quicksort(mylist,0,len(mylist)-1)
    print mylist
    
    貌似简洁了些许。


    吐槽:

    觉得py好美,它的list传进去函数中,就是原始的list,而不是副本。

    如果要看《算法导论》中的伪代码,请看下链接:http://blog.csdn.net/emaste_r/article/details/7100997





    展开全文
  • 主要介绍了python快速排序的实现及运行时间比较,本文通过两种方法给大家介绍,大家可以根据自己需要选择适合自己的方法,对python实现快速排序相关知识感兴趣的朋友一起看看吧
  • python 快速排序使用python实现快速排序方法一方法二 使用python实现快速排序 快速排序,⼜称划分交换排序 1.通过⼀趟排序将要排序的数据分割成独⽴的两部分, 其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩ ...
  • Python快速排序算法

    千次阅读 2017-05-27 17:50:52
    快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分...
  • python实现快速排序算法:def quicksort(arr): if(len(arr)) return arr pivot = arr[len(arr) // 2] # python3用// python2用/ left = [x for x in arr if x ] middle = [x for x in arr
  • 快速排序算法在开发实践中,应用广泛。 这里把边界代码分享一下。 Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32 Type “help”, “copyright”, “credits” ...
  • python快速排序递归与非递归

    千次阅读 2018-10-18 15:06:35
    快速排序递归与非递归pythonpyhton快速排序递归与非递归写在前面快速排序的递归函数快排的切分函数快排的非递归函数完整的源代码 pyhton快速排序递归与非递归 写在前面 众所周知,快速排序相对于选择排序,插入...
  • python 快速排序 代码

    2018-03-21 16:37:03
  • 快速排序 过程图解 ...
  • Python快速排序和冒泡排序(更新中)

    千次阅读 多人点赞 2020-09-16 11:39:50
    快速排序:第1次随机挑选一个数,称为枢值,接下来,将所有要排序的数字分成两部分,第一部分是大于等于枢值的,第二部分是小于枢值的;从上面得到的2堆数字,分别采用第一步的方法各自再找一个枢值,也用同样的方法...
  • python 快速排序

    2017-01-19 14:15:12
    递归实现快速排序法:def quitsort(arr): if len(arr) return arr pivot=arr[len(arr)/2] left=[x for x in arr if x] middle=[x for x in arr if x==pivot] right=[x for x in arr if x
  • 学习python 快速排序

    2015-02-13 17:11:10
    def q(start , end , a): if start>= end : return else : mid = (start+end)/2 i = start+1 j = end key =a[start] while i while i<=end
  • python快速排序的递归实现

    千次阅读 2018-03-14 13:11:06
    更多排序算法请参见我的github: https://github.com/zlsjsj/python-sort/tree/master使用递归算法来实现快速排序,使得代码更加简洁def quicksort(arr): if len(arr) &lt;= 1: return arr #当数组中只包含一...
  • python常用的几种排序方法,这几个方法涉及到冒泡,快速排序,等等.............
  • python快速排序法实现

    2015-08-16 12:30:18
    基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据...
  • 主要利用了行数的递归调用和Python的切片特性,解释一下每行代码的含义: 第1行: #coding:utf-8 指定utf-8 编码 第2行:定义函数名和参数 第3行: 判断列表长度是否小于等于1, 如果小于等于1,直接返回列表 第4行:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,224
精华内容 28,489
关键字:

python快速排序

python 订阅