快速排序

简介

快速排序（Quick Sort）是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

示例

方式1

这种写法的平均空间复杂度为 $O(nlogn)$

def quick_sort_v1(arr: list[int]) -> list[int]:
    if len(arr) < 2:  # 递归终止条件：子数组长度为 0 或 1
        return arr
    
    pivot = arr[0]  # 选择第一个元素为基准值
    left = [i for i in arr[1:] if i <= pivot]  # 小于基准值的元素
    right = [i for i in arr[1:] if i > pivot]  # 大于基准值的元素
    return quick_sort_v1(left) + [pivot] + quick_sort_v1(right)

if __name__ == "__main__":
    print(quick_sort_v1([2,4,1,0,3,5]))

方式2

这种写法的平均空间复杂度为 $O(logn)$

'''
@param nums: 待排序数组
@param left: 数组上界
@param right: 数组下界
'''
def quickSort2(nums, left, right):
    # 分区操作
    def partition(nums, left, right):
        pivot = nums[left]  # 基准值
        while left < right:
            while left < right and nums[right] >= pivot:
                right -= 1
            nums[left] = nums[right]  # 比基准小的交换到前面
            while left < right and nums[left] <= pivot:
                left += 1
            nums[right] = nums[left]  # 比基准大交换到后面
        nums[left] = pivot # 基准值的正确位置，也可以为 nums[right] = pivot
        return left  # 返回基准值的索引，也可以为 return right
    # 递归操作
    if left < right:
        pivotIndex = partition(nums, left, right)
        quickSort2(nums, left, pivotIndex - 1)  # 左序列
        quickSort2(nums, pivotIndex + 1, right) # 右序列
    return nums

Go实现

func quickPartition(src []int, left, right int) int {
	// 基准值
	pivot := src[left]
	for left < right {
		for left < right && src[right] >= pivot {
			right -= 1
		}
		src[left] = src[right] // 比基准值小的交换左边

		for left < right && src[left] <= pivot {
			left += 1
		}
		src[right] = src[left] // 比基准值大的交换到右边
	}
	src[left] = pivot // 基准值的正确位置
	return left       // 返回基准值的索引
}

func quickSort(src []int, left, right int) []int {
	srcLen := len(src)
	if srcLen <= 1 {
		return src
	}
	// left := 0
	// right := srcLen - 1
	if left < right {
		pivotIndex := quickPartition(src, left, right)
		quickSort(src, left, pivotIndex-1)
		quickSort(src, pivotIndex+1, right)
	}

	return src
}

// 基于递归的快速排序
func quickSort2(src []int) []int {
	srcLen := len(src)
	if srcLen <= 1 {
		return src
	}
	pivot := src[0]
	var low, mid, high []int
	for i := 0; i < srcLen; i++ {
		if src[i] < pivot {
			low = append(low, src[i])
		} else if src[i] == pivot {
			mid = append(mid, src[i])
		} else {
			high = append(high, src[i])
		}
	}
	low, high = quickSort2(low), quickSort2(high)
	rst := append(append(low, mid...), high...)
	return rst
}