06. 快速排序

[utterances-bot]

06.快速排序 | 算法通关手册

快速排序 # 1. 快速排序算法思想 # 快速排序（Quick Sort）基本思想： 通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列

https://algo.itcharge.cn/01.Array/02.Array-Sort/06.Array-Quick-Sort/

[WhiteNight123]

三路快排

def quickSort(nums, left, right):
        if left >= right:
          return
        random_index = random.randint(left, right)
        mid = nums[random_index]
        nums[left], nums[random_index] = nums[random_index], nums[left]
        i = left + 1
        j = left
        k = right + 1
        while i < k:
          if nums[i] < mid:
            nums[i], nums[j + 1] = nums[j + 1], nums[i]
            i += 1
            j += 1
          elif nums[i] > mid:
            nums[i], nums[k - 1] = nums[k - 1], nums[i]
            k -= 1
          else:
            i += 1
        nums[left], nums[j] = nums[j], nums[left]
        quickSort(nums, left, j - 1)
        quickSort(nums, k, right)

[AldousShou]

def quick_sort(arr: List[int]) -> List[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 基准数
    left = []
    right = []
    for x in arr[1:]:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)
    return quick_sort(left) + [pivot] + quick_sort(right)

稍微写了下，感觉这样子对新手比较友好一些

[weiyixing]

@AldousShou 快排是原地排序

[hanxiang0227]

@weiyixing 两种有什么区别吗？

[feifangu]

空间复杂度变大了

[WangYan1003]

快排不应该是坑位互换吗?如果示例采用: [4,7,5,8,6,1,3]，是不是就会有问题的？

[iamruifeng]

必须先移动右指针，再移动左指针，这样基准元素才能按顺序换到

[Paden79555]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

[Paden79555]

随机数优化

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)