快速排序是什么？快速排序的JS实现

快速排序是一种基于“分而治之”策略的高效排序算法，通过选择基准、分区和递归排序三个核心步骤，将数组逐步分解为有序子数组并合并结果。

• 工作原理：

  选择基准（Pivot Selection）：从数组中选取一个元素作为基准（如第一个、最后一个、中间或随机元素）。基准的选择直接影响分区效率，随机或三数取中法可降低最坏情况概率。

  分区（Partitioning）：将数组划分为两部分，左边元素均小于基准，右边元素均大于或等于基准。分区后，基准位于最终有序位置。

  递归排序（Recursive Sort）：对左右子数组重复上述过程，直至子数组长度为1或0，此时整个数组有序。

• 性能表现：

  时间复杂度：

  平均情况：O(n log n)。每次分区遍历子数组（O(n)），问题规模减半（log n层递归）。

  最好情况：O(n log n)。每次分区完美一分为二（如基准为中位数）。

  最坏情况：O(n²)。当基准为极端值（如已排序数组选首/尾元素），每次分区仅减少1个元素。

  空间复杂度：

  平均情况：O(log n)。递归调用栈深度为log n。

  最坏情况：O(n)。递归深度达n（如最坏时间复杂度场景）。

• JavaScript实现：

  非原地版本（直观但内存消耗较高）：function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[arr.length - 1]; const remainingArr = arr.slice(0, -1); const left = [], right = []; for (let i = 0; i < remainingArr.length; i++) { if (remainingArr[i] < pivot) left.push(remainingArr[i]); else right.push(remainingArr[i]); } return [...quickSort(left), pivot, ...quickSort(right)];}

  原地版本（高效，通过指针交换减少内存使用）：function quickSortInPlace(arr, low, high) { if (low < high) { const pi = partition(arr, low, high); quickSortInPlace(arr, low, pi - 1); quickSortInPlace(arr, pi + 1, high); }}function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1;}// 调用示例：// const arr = [3, 6, 8, 10, 1, 2, 1];// quickSortInPlace(arr, 0, arr.length - 1);

• 常见优化技巧：

  优化基准选择：

  随机选择基准：降低最坏情况概率。

  三数取中法：选首、中、尾元素的中位数作为基准，减少极端值影响。

  处理小规模子数组：当子数组长度小于阈值（如10）时，切换为插入排序，减少递归开销。

  尾递归优化：通过迭代或手动维护栈模拟递归，避免栈溢出。

  三路分区：将数组分为小于、等于、大于基准的三部分，跳过相等元素，提升重复元素处理效率。

快速排序凭借其平均O(n log n)的时间复杂度和“分而治之”的优雅设计，成为实际应用中最常用的排序算法之一。通过合理选择基准和优化分区策略，可进一步提升其稳定性和性能。