快速排序

时间复杂度：

• 平均 O(nlogn)
• 最佳 O(nlogn)
• 最坏 O(n^2)

空间复杂度：

• 平均 O(logn)
• 最佳 O(logn)
• 最坏 O(n)

核心思想：分治法 (Divide and Conquer) + 基准点 (Pivot)

快速排序的目标是选择一个元素作为“基准 (Pivot)”，然后将数组重新排列，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。完成这次“分区 (Partition)”后，基准元素就到达了它最终应该在的位置。然后，再对左右两个子数组递归地执行相同的过程，直到整个数组有序。

经典实现

比它小的放左边，比他大的放右边。

const quickSortEasy = (arr) => {
    if(arr.length <= 1){
        return arr;
    }

    let left = [];
    let right = [];
    let pivot = arr[0];
    for(let i=1;i<arr.length;i++){
        if(arr[i]<pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }

    return [...quickSortEasy(left), pivot, ...quickSortEasy(right)];
}

console.log(quickSortEasy([4, 2, 7, 1, 3, 6, 5]))

Lomuto分区写法：

这里privot表示分区之后，基准元素的位置； 反转就是往前往后，各自分区呗

一、基本原理 在这个实现中，pivot被选为最右边的元素(nums[right]) 目标是将数组分成三部分:

• 左侧：所有小于pivot的元素
• 中间：pivot元素本身
• 右侧：所有大于等于pivot的元素

二、代码执行流程解析

1. 指针说明

   • i 跟踪"小于pivot区域"的边界，初始为left-1 (区域为空)
   • j 是当前正在检查的元素，从left开始遍历到right-1

2. 条件判断: if nums[j] < nums[right]

   • nums[right]是pivot元素
   • 当nums[j] < pivot时，说明这个元素应该在pivot左侧
   • 这时需要: a. i++ (扩展"小于pivot区域") b. 交换nums[i]和nums[j] (将当前元素放入小区域)

3. 当不满足条件时 (nums[j] >= pivot)

   • 不执行任何操作
   • 元素保持原位，实际上留在了"大于等于pivot区域"

4. 最终交换: nums[i+1], nums[right] = nums[right], nums[i+1]

   • 循环结束后，[left..i]的元素都小于pivot
   • i+1位置正是pivot应该在的位置
   • 交换后，pivot正好位于小区域和大区域之间

const pivot = partition(nums, left, right)
quickSort_(nums, left, pivot-1)
quickSort_(nums, pivot+1, right)

// 使用right来存基准值
func quickSort(nums []int){

    var quickSort_ func(nums []int, left int, right int)

    quickSort_ = (nums []int, left int, right int){

        if(left<right){
            const pivot = partition(nums, left, right)
            quickSort_(nums, left, pivot-1)
            quickSort_(nums, pivot+1, right)
        }
    }
    quickSort_(nums, 0, len(nums)-1)
}

func partition(nums []int, left int, right int){
    i := left-1

    for j=left;j<right;j++{
        if nums[j] < nums[right] {
            i++;
            nums[i],nums[j] = nums[j],nums[i]
        }
    }
    nums[i+1], nums[right] = nums[right], nums[i+1]
    
    return i+1; // i+1 是 privot的位置
}

// 一个left一个right
func partition(nums []int, left int, right int){
     
    i := left - 1
    for j=0;j<rigtht;j++{
        if nums[j]<right{
            i++
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    nums[right], nums[i+1] = nums[i+1], nums[right]
    return i+1;
}

func partition(nums []int, left int, right int){
    
    pivot := nums[left]

    for left < right {

        for left < right && nums[right] >= nuns[pivot]{
            right--;
        }
        nums[left] = nums[right]

        for left < right && nums[left] <= nuns[pivot]{
            left++;
        }
        nums[right] = nums[left]
    }
    nums[left] = pivot
    return left;
}