带你读《图解算法小抄》十四、排序(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