您的位置：首页 > 脚本大全 > > 正文

python排序方法简单（快速排序的四种python实现推荐）

更多 时间：2021-10-21 08:18:40 类别：脚本大全 浏览量：1294

python排序方法简单

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

快速排序算法，简称快排，是最实用的排序算法，没有之一，各大语言标准库的排序函数也基本都是基于快排实现的。

本文用python语言介绍四种不同的快排实现。

1. 一行代码实现的简洁版本

  • ?
  • 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. 网上常见的快排实现

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
    		•
  • 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.《算法导论》中的快排程序

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
    		•
  • 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。

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
    		•
  • 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实现快速排序算法详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对开心学习网网站的支持！

    原文链接：https://blog.csdn.net/razor87/article/details/71155518

    标签：Python 快速排序
  • 上一篇：mac使用docker部署项目（如何在mac上用docker对Oracle进行部署使用）
  • 下一篇：python数据分析删除重复值（Python3实现从排序数组中删除重复项算法分析）
    • 您可能感兴趣
    首页 编程学习 Web前端 数据库 软件设计
    开心学习 ©2013-2021 保留所有权利