时间复杂度O(n2), 最优时间复杂度O(n)
// 快速排序 // 先整体有序，后局部有序 // 三个需要注意的地方： // 1.pivot是值而不是index // 2.left和right比较要取等号 // 3.a[left/right] 和 pivot 比较不取等号 function quickSort(nums) { if (nums === null || nums.length === 0) return; helper(nums, 0, nums.length - 1); function helper(nums, start, end) { if (start >= end) return; let left = start; let right = end; // 取一个中间值来进行对比，这里取中点上的数 // 1.注意：这里取的是value而不是index const pivot = nums[Math.floor((start + end) / 2)]; // 2.注意：是left <= right 而不是 left < right，这样为了两段没有交集 while (left <= right) { // 找到一个大于等于pivot的值 // 3.注意：a[left] < pivot 而不是 a[left] <= pivot while (left <= right && nums[left] < pivot) { left++; } // 找到一个小于等于pivot的值 while (left <= right && nums[right] > pivot) { right--; } // 交换两个数 if (left <= right) { let temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } // 此处left和right已经交叉 helper(nums, start, right); helper(nums, left, end); } }