daily note

2026-5-18

今天记录一下昨天写的一道快速排序和快速选择的题目，之前都是用python写的，现在要转成c++了的，感觉还是不是很适应的，所以尽量坚持每天记录下来。

• 快速排序

void quick_sort(vector<int> &nums, int left, int right){
    if (left >= right){
        return;
    }
    int pivot = nums[left+(right-left)/2];
    int i = left - 1;
    int j = right + 1;
    while(i < j){
        do i++; while(nums[i] < pivot);
        do j--; while(nums[j] > pivot);
        if (i < j){
            swap(nums[i], nums[j]);
        }
    }
    quick_sort(nums, left, j);
    quick_sort(nums, j+1, right);
}

• 快速排序（python）

def quick_sort(nums,left,right):
    if left>=right:
        return
    pivot = nums[left+(right-left)//2]
    nums_left = [x for x in nums if x < pivot]
    nums_mid = [x for x in nums if x == pivot]
    nums_right = [x for x in nums if x > pivot]
    return quick_sort(nums_left,0,len(nums_left)-1) + nums_mid + quick_sort(nums_right,0,len(nums_right)-1)

• 快速选择

int quikc_select(vector<int> &nums, int left; int right, int k){
    if (left >= right){
        return nums[left];
    }

    int pivot = nums[left+(right-left)/2];
    int i = left - 1;
    int j = right + 1;
    while(i < j){
        do i++; while(nums[i] < pivot);
        do j--; while(nums[j] > pivot);
        if (i < j){
            swap(nums[i], nums[j]);
        }
    }
    if(j >= k){
        return quikc_select(nums, left, j, k);
    }
    else{
        return quikc_select(nums, j+1, right, k);
    }
}