快速排序

时间复杂度：

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

经典实现

一、双指针分区法的核心思想 这种方法也称为"挖坑填数法"，其工作原理是：

1. 选择一个基准值(pivot)并"挖出"，形成第一个"坑"
2. 通过交替移动左右指针，找到不符合排序要求的元素
3. 用这些元素填补已有的"坑"，同时在原位置形成新的"坑"
4. 最后将基准值放回最终位置

二、代码流程详解 初始状态：

• pivot = nums[left] 记录基准值
• 此时left位置形成第一个"坑"

循环过程：

1. 从右向左扫描，找到第一个小于pivot的元素

   for left<right && nums[right]>=pivot {
       right--; // 继续向左找
   }

   找到后，right停在这个元素位置

2. 关键步骤：nums[left] = nums[right]

   • 将找到的小元素放入left位置的"坑"中
   • 同时，right位置变成新的"坑"

3. 从左向右扫描，找到第一个大于pivot的元素

   for left<right && nums[left]<=pivot {
       left++; // 继续向右找
   }

   找到后，left停在这个元素位置

4. nums[right] = nums[left]

   • 将找到的大元素放入right位置的"坑"中
   • 同时，left位置变成新的"坑"

循环结束后：

• nums[left] = pivot; // 将基准值放入最终位置

func quickSort(nums, k){

    var quickSort_ func(nums []int, left int, right int)
    
    quickSort_ = func(nums []int, left int, right int){
        if(left >= height){
            return;
        }
        pivot := partition(nums, left, right)
        quickSort_(nums, left, pivot-1)
        quickSort_(nums, pivot+1, right)
    }
    quickSort_(nums,0, len(nums)-1)
    return nums;
}

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

    let pivot = nums[left];

    for left<right {

        for left<right && nums[right]>=pivot { // 找到第一个小于它的值
            height--;
        }
        nums[left] = nums[right];

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

    return left; // low存的是pivot
}

初始状态：arr = [4, 1, 7, 3, 8, 2, 6, 5], low = 0, high = 7
pivot = arr[low] = 4

循环开始：
1. 从右向左：high = 7, arr[7] = 5 > 4, high--
2. high = 6, arr[6] = 6 > 4, high--
3. high = 5, arr[5] = 2 < 4, arr[low] = arr[high], arr = [2, 1, 7, 3, 8, 2, 6, 5]
4. 从左向右：low = 0, arr[0] = 2 < 4, low++
5. low = 1, arr[1] = 1 < 4, low++
6. low = 2, arr[2] = 7 > 4, arr[high] = arr[low], arr = [2, 1, 7, 3, 8, 7, 6, 5]
7. 从右向左：high = 5, arr[5] = 7 > 4, high--
8. high = 4, arr[4] = 8 > 4, high--
9. high = 3, arr[3] = 3 < 4, arr[low] = arr[high], arr = [2, 1, 3, 3, 8, 7, 6, 5]
10. 从左向右：low = 2, arr[2] = 3 < 4, low++
11. low = 3, arr[3] = 3 < 4, low++
12. low = 4, arr[4] = 8 > 4, arr[high] = arr[low], arr = [2, 1, 3, 3, 8, 7, 6, 5]
...

最终：low = high = 4, arr[low] = pivot = 4
结果：arr = [2, 1, 3, 3, 4, 7, 6, 5]
pivotIndex = 4

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;
}