欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python 实现快速排序

程序员文章站 2022-05-18 21:18:34
思想 从待排序列中挑出一个元素,作为"基准"(pivot),通过一趟排序,把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。对前后两个区间重复此操作,直到前后分区的带下是0或1结束。每一次都确定待排序列中一个元素的 ......

思想

从待排序列中挑出一个元素,作为"基准"(pivot),通过一趟排序,把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。对前后两个区间重复此操作,直到前后分区的带下是0或1结束。每一次都确定待排序列中一个元素的位置。

def quicksort(input_list, left, right):
    def divsion(input_list, left, right):
        # pivot为基准
        # pivot = input_list[left]
        while left < right:
            while left < right and input_list[right] >= input_list[left]:
                right -= 1
            # 找到一个元素小于基准元素,则把该元素放在前面
            t=input_list[left]
            input_list[left] = input_list[right]
            input_list[right]=t
            while left < right and input_list[left] <= input_list[right]:
                left += 1
            # 找到一个元素大于基准元素,则把该元素放到后面
            t = input_list[right]
            input_list[right] = input_list[left]
            input_list[left]=t
        # 当left = right,即此时,left位置的左边都比基准元素小,
        # left元素右边都比基准元素大,此时把基准元素放入该位置,
        # 即该位置就是基准元素的最终排序位置
        return left

    if left < right:
        pivot_index = divsion(input_list, left, right)
        print("每执行本次分区后的结果:")
        print(input_list)
        # 用分治法对待排元素的左右两边分别递归进行quicksort
        quicksort(input_list, left, pivot_index - 1)
        quicksort(input_list, pivot_index + 1, right)


if __name__ == '__main__':
    input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
    print("input_list:")
    print(input_list)
    quicksort(input_list, 0, len(input_list) - 1)
    print("sorted_list:")
    print(input_list)