欢迎访问优讯网!
您当前的位置:首页 > 爱编程

Python实现快速排序

时间:2019-09-30 08:19:00  来源:优讯网  作者:小卡司  浏览次数:
def sort( a):
    return quick_sort( a, 0, len(a)-1)

def quick_sort( a, left, right):
    if( left < right):
        partitionIndex = partition( a, left, right)
        quick_sort(a, left, partitionIndex-1)
        quick_sort(a, partitionIndex+1, right)
    return a

def partition( a, left, right):
    pivot = left
    index = pivot + 1
    for i in range( index, right+1):
        if( a[i] < a[pivot]):
            swap( a, i, index)
            index += 1
    swap( a, pivot, index-1)
    return index-1

def swap( a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
  • 从数列中挑出一个元素,称为 “基准”(pivot)
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
  • 在每次的迭代(iteration)中,至少会把一个元素摆到其最后的位置去
  • 平均时间复杂度:O(n㏒₂n)
  • 最坏时间复杂度:O(n²)
  • 最好时间复杂度:O(n㏒₂n)
  • 空间复杂度:O(n㏒₂n)
  • 稳定性:不稳定
以上就是关于 Python实现快速排序 的全部内容了,喜欢的小伙伴别忘了点赞分享一下哦,关注优讯网,优讯有你更精彩!
转载自: https://my.oschina.net/hbuswstcly/blog/3112527
版权归原作者所有,如有侵权请联系我们删除。
来顶一下
返回首页
返回首页
推荐资讯
计算机的正确使用姿势 电脑痴如何正确的使用电脑
计算机的正确使用姿势
好用的后台管理的前端框架模版H-ui H-ui框架模版分享
好用的后台管理的前端
微信电脑多开方法 无需辅助电脑版微信双开方法分享
微信电脑多开方法 无
Python实现网站百度主动推送 python实现主动推送网站地图
Python实现网站百度主
相关文章
栏目更新
栏目热门