python-快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python-快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1941字，纯文字阅读大概需要3分钟。

内容图文

核心思想：取一个初始值，将数组中比该值小的放在其左边，比其大的放在右边， 再对左、右子数组进行相同操作，直到数组排好序。

def quicksort(nums):
    l = 0
    r = len(nums) - 1
    _quicksort(nums,l,r)
def _quicksort(nums,l,r):
    if l < r:
        p = partition(nums,l,r)
        _quicksort(nums,l,p-1)
        _quicksort(nums,p+1,r)
def partition(nums,l,r):
    base = nums[l]
    j = l+1
    for i in range(l+1,r+1):
        if nums[i]<base:
            nums[i],nums[j]=nums[j],nums[i]
            j+=1
    nums[l],nums[j-1]=nums[j-1],nums[l]
    return j-1

nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)

改进：随机选择初始值，避免数组有序使算法退化。从两边开始遍历，减少遍历时间。

import random
def quicksort(nums):
    l = 0
    r = len(nums) - 1
    _quicksort(nums,l,r)
def _quicksort(nums,l,r):
    if l < r:
        p = partition(nums,l,r)
        _quicksort(nums,l,p-1)
        _quicksort(nums,p+1,r)
def partition(nums, l, r):
    ind = random.randint(l, r)
    nums[l], nums[ind] = nums[ind], nums[l]
    base = nums[l]
    i, j = l+1, r
    while True:
        while i <= r and nums[i] < base:  # 不能改为nums[i] <= base          
            i += 1
        while j >= l + 1 and nums[j] > base:  # 不能改为nums[j] >= base.
            j -= 1
        if i > j:
            break
        else:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    nums[j], nums[l] = nums[l], nums[j]
    return j

nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)

改进：三路快排，用于解决数组中有较多重复的值。

import random
def quicksort(nums):
    l = 0
    r = len(nums) - 1
    _quicksort(nums,l,r)
def _quicksort(nums,l,r):
    if l < r:
        lt,gt = partition(nums,l,r)
        _quicksort(nums,l,lt-1)
        _quicksort(nums,gt,r)
def partition(nums, l, r):
    ind = random.randint(l, r)
    nums[l], nums[ind] = nums[ind], nums[l]
    base = nums[l]
    lt = l  # nums[l+1...lt] < base
    gt = r + 1  # nums[gt...r] > base
    i = l + 1  # nums[lt+1...i] == base
    while (i < gt):
        # i==gt时表示已经比较结束
        if (nums[i] < base):
            nums[i], nums[lt+1] = nums[lt+1], nums[i]
            lt += 1
            i += 1
        elif (nums[i] > base):
            nums[i], nums[gt-1] = nums[gt-1], nums[i]
            gt -= 1
        else:  # nums[i] == base
            i += 1
    nums[l], nums[lt] = nums[lt], nums[l]
    return lt, gt

nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)

 

内容总结

以上是互联网集市为您收集整理的python-快速排序全部内容，希望文章能够帮你解决python-快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---