带你读《图解算法小抄》十四、排序（9）https://developer.aliyun.com/article/1348141?groupCode=tech_library
2）快速排序的优化技巧
尽管快速排序是一种高效的算法，但在某些情况下，其性能可能有所下降。为了克服这些问题，我们可以使用以下优化技巧：
随机选择pivot
当数组已经有序时，选择中间位置的元素作为pivot会导致分割出的两个子数组大小差异很大，从而降低算法性能。为了解决这个问题，可以使用随机选择pivot的方法。通过随机选择pivot，可以减少特定情况下的不利影响，提高整体性能。
下面是在JavaScript中实现随机选择pivot的代码示例：
function getRandomPivot(arr, start, end) { const randomIndex = Math.floor(Math.random() * (end - start + 1)) + start; [arr[randomIndex], arr[end]] = [arr[end], arr[randomIndex]]; return partition(arr, start, end); } function quickSortRandomPivot(arr, start = 0, end = arr.length - 1) { if (start < end) { const pivotIndex = getRandomPivot(arr, start, end); quickSortRandomPivot(arr, start, pivotIndex - 1); quickSortRandomPivot(arr, pivotIndex + 1, end); } return arr; }
三数取中法
快速排序的性能在某些特定情况下可能会下降，如当数组已经有序或接近有序时。为了解决这个问题，可以使用"三数取中法"来选择pivot。该方法从子数组的起始、中间和末尾位置选择三个元素，并将它们排序后选择中间的元素作为pivot。
function getMedianOfThree(arr, start, end) { const mid = Math.floor((start + end) / 2); if (arr[start] > arr[mid]) { [arr[start], arr[mid]] = [arr[mid], arr[start]]; } if (arr[start] > arr[end]) { [arr[start], arr[end]] = [arr[end], arr[start]]; } if (arr[mid] > arr[end]) { [arr[mid], arr[end]] = [arr[end], arr[mid]]; } return mid; } function quickSortMedianOfThree(arr, start = 0, end = arr.length - 1) { if (start < end) { const pivotIndex = getMedianOfThree(arr, start, end); const pivot = arr[pivotIndex]; let left = start; let right = end - 1; while (left <= right) { while (arr[left] < pivot) { left++; } while (arr[right] > pivot) { right--; } if (left <= right) { [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; } } [arr[left], arr[pivotIndex]] = [arr[pivotIndex], arr[left]]; quickSortMedianOfThree(arr, start, left - 1); quickSortMedianOfThree(arr, left + 1, end); } return arr; }
带你读《图解算法小抄》十四、排序（11）https://developer.aliyun.com/article/1348139?groupCode=tech_library
