python 快速排序

**快速排序（Quicksort）是对冒泡排序的一种改进。 **

• 快速排序由C. A. R. Hoare在1960年提出。
• 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法实现：

• （1）首先设定一个分界值，通过该分界值将数组分为左右两部分。
• （2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
• （3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
• (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

程序实现：

解法一：双指针法（两种写法）

# 挖坑法
def Quicksort_first(nums):
    if len(nums) <=1:
        return  nums
    left = 0
    right = len(nums)-1
    point = nums[0]  # 此时left位置元素为空
    while left < right:
        while left < right and nums[right] >= point:
            right -= 1
        nums[left] = nums[right]  # 将数据插入到left空位里，则此时right位置元素为空
        while left <right and nums[left] < point:
            left += 1
        nums[right] = nums[left]  # 将数据插入到right空位
    nums = Quicksort_first(nums[0:right]) + [point] + Quicksort_first(nums[right+1:])
    return nums


def Quicksort_second(nums):
    if len(nums) >=2:
        mid = nums[len(nums)//2]
        left, right = [], []
        nums.remove(mid)
        for item in nums:
            if item >= mid:
                right.append(item)
            else:
                left.append(item)
        return Quicksort_second(left) + [mid] + Quicksort_second(right)
    else:
        return  nums
nums = [2,3,4,57,9,34,5]
result =Quicksort_first(nums)
print(result)

特殊情况讨论，不同程序设计。出现无限递归

left =0

当我们从left=0开始遍历时，会出现一个很特殊的情况。
当分界值为nums中最小元素时，且程序设计如下第一个，那么在退出while循环时，left=0，则会无限递归下去。

def Quicksort_first(nums):
    if len(nums) <=1:
        return nums
    left = 0
    right = len(nums)-1
    point = nums[0]
    if len(nums) == 2:
        if nums[0] < nums[1]:
            return nums
        else:
            return nums[::-1]
    while left < right:
        while left <right and nums[left] < point:
            left += 1
        while left < right and nums[right] >= point:
            right -= 1
        nums[left], nums[right] = nums[right], nums[left]  # 互换数据
    print(nums)
    print(right)
    nums = Quicksort_first(nums[:left]) + Quicksort_first(nums[left:])
    return nums

下面这个程序不会出现上述异常。
因为，当分界值为nums中最小元素时，且程序设计如下第一个，那么在退出while循环时，left=0，则不会无限递归下去。

def Quicksort_first(nums):
    if len(nums) <= 1:
        return nums
    left = 0
    right = len(nums)-1
    point = nums[0]

    while left < right:
        while left < right and nums[right] >= point:
            right -= 1
        while left <right and nums[left] < point:
            left += 1
        nums[left], nums[right] = nums[right], nums[left]  # 互换数据
    print(nums)
    print(right)
    nums = Quicksort_first(nums[:left+1]) + Quicksort_first(nums[left+1:])
    return nums

left = 1

def Quicksort_first(nums):
    if len(nums) <=1:
        return nums
    left = 1
    right = len(nums)-1
    point = nums[0]
    while left < right:
        while left < right and nums[right] >= point:
            right -= 1
        while left <right and nums[left] < point:
            left += 1
        nums[left], nums[right] = nums[right], nums[left]  # 互换数据
    print(nums)
    print(right)
    nums = Quicksort_first(nums[1:right+1]) + [point]  + Quicksort_first(nums[right+1:])
    return nums

解法二：单指针法

def Quicksort_third(nums):
    if len(nums) <= 1:
        return nums
    key = nums[0]
    point = 0
    for i in range(1,len(nums)):
        if nums[i] <= key:
            point += 1
            nums[point], nums[i] =  nums[i], nums[point]
    return Quicksort_third(nums[1:point+1]) + [key] + Quicksort_third(nums[point+1:])

总结：

无论是单指针法还是双指针法，其最核心的思想都是右边元素小于分界值，左边元素大于分界值。