快速排序

题目

实现一个快速排序

思路

待排序的数列中，我们首先要找一个数字作为基准数（pivot,直译是中心枢纽， 这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区（partition）找出基准数，然后移动，直到各个分区只有一个数时为止。

第一个数一般选择中位数，涉及到中位数算法，较复杂。
三点中值算法：选择第0个、中间的、最后的，在3个数中选择中间数

代码

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)
def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            # 控制升序还是降序
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i+1]
    # print(array)
    return i + 1
if __name__ == "__main__":
    array = [10, 5, 3, 1, 7]
    quick_sort(array, 0, len(array)-1)
    print(array)

def _quick_sorted(nums:list) -> list:
    pivot = nums[0]
    left_nums = _quick_sorted([num for num in nums[1:] if num < pivot])
    right_nums = _quick_sorted([num for num in nums[::-1] if num >= pivot])
    return left_nums+ [pivot] + right_nums

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q)
        quick_sort(array, q + 1, r)
def partition(array, l, r):
    pivot = array[l]
    i = l + 1
    for j in range(l+1, r):
        if array[j] < pivot:
            array[i], array[j] = array[j], array[i]
            i += 1
    array[i - 1], array[l] = array[l], array[i - 1]
    return i - 1
if __name__ == "__main__":
    array = [3, 5, 7, 1, 10]
    quick_sort(array, 0, len(array))
    print(array)