带你读《图解算法小抄》十四、排序（8）https://developer.aliyun.com/article/1348142?groupCode=tech_library
5.快速排序
快速排序是一种分而治之的算法。快速排序首先将一个大数组分成两个较小的子数组：比某个数小的元素和比某个数大的元素。然后快速排序可以递归地对子数组进行排序。
步骤是：
从数组中选择一个元素，称为基点
分区：对数组重新排序，使所有值小于基点的元素都在它左边，而所有值大于基点的元素都在它右边（相等的值可以放在任何一边）。在此分区之后，基点处于其最终位置（左边和右边的中间位置）。这称为分区操作。
递归地将上述步骤应用于左边的数组和右边的数组。
快速排序算法的动画可视化。水平线是基点值。
1）排序流程
快速排序是一种基于分治法的排序算法，其基本原理如下：
选择pivot：从待排序数组中选择一个元素作为pivot（枢纽元素）。通常，我们选择数组的中间元素作为pivot，以实现较好的平衡性。
分割数组：将数组中的元素按照与pivot的大小关系，分割为两个子数组：小于pivot的子数组和大于pivot的子数组。这一步骤通常称为partition（分割）。
为了实现分割，我们使用两个指针：左指针和右指针。左指针从数组的起始位置开始，右指针从数组的末尾位置开始。
左指针向右移动，直到找到一个大于等于pivot的元素。
右指针向左移动，直到找到一个小于等于pivot的元素。
如果左指针仍然在右指针的左侧，则交换左右指针所指的元素。
重复上述步骤，直到左指针大于等于右指针。
递归排序子数组：对分割得到的两个子数组（小于pivot的子数组和大于pivot的子数组）进行递归排序。递归调用快速排序算法即可。
合并结果：将排序后的子数组合并起来，得到最终的排序结果。合并的过程可以通过将左子数组、pivot和右子数组依次连接起来来实现。
function quickSort(arr) { if (arr.length <= 1) { return arr; } // 选择pivot（通常是数组的中间元素） const pivot = arr[Math.floor(arr.length / 2)]; // 分割数组为两个子数组 const left = []; const right = []; for (let i = 0; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else if (arr[i] > pivot) { right.push(arr[i]); } } // 递归地对子数组进行排序，并将结果合并 return quickSort(left).concat(pivot, quickSort(right)); } // 示例用法const array = [5, 8, 2, 1, 6, 3, 9, 4, 7];const sortedArray = quickSort(array); console.log(sortedArray);
带你读《图解算法小抄》十四、排序（10）https://developer.aliyun.com/article/1348140?groupCode=tech_library
