快速排序

基本思路

先选择一个基准值pivot，让数组中其他元素与pivot相比较，比他小的放左边，比他大的放右边，递归实现，知道左右数组只剩一个为止

实现

function quickSort(nums){
	// 基准情况：如果数组长度小于等于1，直接返回
    if (nums.length <= 1) {
        return nums;
    }
	let pivot=nums[0];//基准值指定为数组第一个
	let left=[];
	let right=[];
	for(let i=1;i<nums.length;i++){
		if(nums[i]<pivot){
			left.push(nums[i])
		}else{
			right.push(nums[i])
		}
	}
	return [...quickSort(left),pivot,...quickSort(right)];
}

时间/空间复杂度分析

快速排序时间，空间复杂度分析

• 时间复杂度：
  • 平均情况：O(n log n)
  • 最坏情况（已有序）：O(n²)（可通过随机选择基准优化）
• 空间复杂度：O(log n)（递归调用栈）
• 稳定性：不稳定

reference