python实现快速排序的两种方法

python基础

浏览数:19

2020-6-17

AD:资源代下载服务

代码环境:python3.6

递归实现

步骤:

  1. 从序列中挑出任意一个元素为pivot,此处选择序列最后一个元素,如果更改,需要相应变更以下步骤内容;
  2. 设置两个指针leftright,指向序列的最左和最右两个元素;
  3. left开始,找到第一个比pivot大的元素;切换到right,找到第一个比pivot小的元素;
  4. leftright此时指向的元素互换;
  5. 重复1-4步骤,直到left==right,将pivotleft对应的元素互换,这样以pivot分割左右两个区,左边元素都比pivot小,右边元素都比pivot大;
  6. 将两个分区分别递归重复1-5步骤,直到不可再分区,递归条件就是start<end

算法实现:

def partition(mylist, start, end):
    # 若选其他元素作为pivot,下面的while内容需要相应更改
    pivot = mylist[end]
    left = start
    right = end

    while left < right:
        while left < right and mylist[left] <= pivot:
            left += 1
        while left < right and mylist[right] >= pivot:
            right -= 1
        if left != right:
            mylist[left], mylist[right] = mylist[right], mylist[left]

    mylist[end], mylist[left] = mylist[left], pivot
    return left


def quick_sort(mylist, start, end):
    """
    mylist: 待排序的 list
    start: mylist第一个元素索引
    end: mylist最后一个元素索引
    """
    if start < end:
        mid = partition(mylist, start, end)
        quick_sort(mylist, start, mid - 1)
        quick_sort(mylist, mid + 1, end)


if __name__ == "__main__":
    mylist = [12, 33, 199, 0, 54, 77, 11, 54, 9, 7]
    quick_sort(mylist, 0, len(mylist) - 1)
    print(f'快速排序后:{mylist}')

非递归实现

绝大多数用递归实现的问题,都可以用的方式来代替。

为什么?因为我们代码中一层层的方法调用,本身就是一个函数栈,每次进入一个新方法,就相当于入栈;每次有方法返回,就相当于出栈。

所以,我们可以利用栈存储每一次调用方法的参数。

算法实现:

class Stack():
    """简单实现一个栈,本质就是个list"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()


# 此方法与上面例子一样,保持不变
def partition(mylist, start, end):
    # 若选其他元素作为pivot,下面的while内容需要相应更改
    pivot = mylist[end]
    left = start
    right = end

    while left < right:
        while left < right and mylist[left] <= pivot:
            left += 1
        while left < right and mylist[right] >= pivot:
            right -= 1
        if left != right:
            mylist[left], mylist[right] = mylist[right], mylist[left]

    mylist[end], mylist[left] = mylist[left], pivot
    return left


def quick_sort(mylist):
    stack = Stack()
    start = 0
    end = len(mylist) - 1

    if start < end:
        stack.push((start, end))
        while not stack.is_empty():
            start, end = stack.pop()
            mid = partition(mylist, start, end)
            if start < mid - 1:
                stack.push((start, mid - 1))
            if mid + 1 < end:
                stack.push((mid + 1, end))

作者:oldk