快速排序的四种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 item in array[1:] if item > array[0]])

2. 网上常见的快排实现

def quick_sort(array, left, right):
  if left >= right:
    return
  low = left
  high = right
  key = array[low]
  while left < right:
    while left < right and array[right] > key:
      right -= 1
    array[left] = array[right]
    while left < right and array[left] <= key:
      left += 1
    array[right] = array[left]
  array[right] = key
  quick_sort(array, low, left - 1)
  quick_sort(array, left + 1, high)

由于快排是原地排序，因此不需要返回array。

array如果是个列表的话，可以通过len(array)求得长度，但是后边递归调用的时候必须使用分片，而分片执行的原列表的复制操作，这样就达不到原地排序的目的了，所以还是要传上边界和下边界的。

3.《算法导论》中的快排程序

def quick_sort(array, l, r):
  if l < r:
    q = partition(array, l, r)
    quick_sort(array, l, q - 1)
    quick_sort(array, q + 1, r)

def partition(array, l, r):
  x = array[r]
  i = l - 1
  for j in range(l, r):
    if array[j] <= x:
      i += 1
      array[i], array[j] = array[j], array[i]
  array[i + 1], array[r] = array[r], array[i+1]
  return i + 1

这个版本跟上个版本的不同在于分片过程不同，只用了一层循环，并且一趟就完成分片，相比之下代码要简洁的多了。

4. 用栈实现非递归的快排程序

先说两句题外话，一般意义上的栈有两层含义，一层是后进先出的数据结构栈，一层是指函数的内存栈，归根结底，函数的内存栈的结构就是一个后进先出的栈。汇编代码中，调用一个函数的时候，修改的也是堆栈指针寄存器ESP，该寄存器保存的是函数局部栈的栈顶，另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间，其组织结构是否也是一个完全二叉树呢？

高级语言将递归转换为迭代，用的也是栈，需要考虑两个问题:

1）栈里边保存什么？

2）迭代结束的条件是什么？

栈里边保存的当然是需要迭代的函数参数，结束条件也是跟需要迭代的参数有关。对于快速排序来说，迭代的参数是数组的上边界low和下边界high，迭代结束的条件是low == high。

def quick_sort(array, l, r):
  if l >= r:
    return
  stack = []
  stack.append(l)
  stack.append(r)
  while stack:
    low = stack.pop(0)
    high = stack.pop(0)
    if high - low <= 0:
      continue
    x = array[high]
    i = low - 1
    for j in range(low, high):
      if array[j] <= x:
        i += 1
        array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    stack.extend([low, i, i + 2, high])

另外，当数组下标为-1时，C++、Java等语言中会报错，但python中访问的是最后一个元素，所以如果程序写错了，可能其他语言会报错，但python会输出一个错误的结果。

以上所述是小编给大家介绍的python实现快速排序算法详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

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

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

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

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

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

  • 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实现的插入排序，冒泡排序，快速排序，选择排序算法示例

    本文实例讲述了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实现快速排序的示例(二分法思想)

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

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

  • 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一行代码实现快速排序的方法

    今天将单独为大家介绍一下快速排序! 一.算法介绍 排序算法(Sorting algorithm)是计算机科学最古老.最基本的课题之一.要想成为合格的程序员,就必须理解和掌握各种排序算法.其中"快速排序"(Quicksort)使用得最广泛,速度也较快.它是图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的. 二.算法原理 快排的实现方式多种多样,猪哥给大家写一种容易理解的:分治+迭代,只需要三步: 在数列之中,选择一个元素作为"基准"(pivot

  • 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

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

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

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

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

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

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

  • 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

随机推荐