【算法（三·四）：分治思想——快速排序】_快速排序 分治

算法介绍

快速排序是基于分治策略的一个经典算法。通过选择一个元素作为基准（也称“主元”）（pivot），将待排序的数组分成两个子数组，一个包含所有小于基准的元素，另一个包含所有大于基准的元素，然后递归地对这两个子数组进行快速排序，从而达到整个数组的排序。由于其高效性，快速排序被广泛认为是实际应用中最快的通用排序算法。其与归并排序在分治思想上的不同点在于，归并排序是“简化分解，侧重合并”，而快速排序是“侧重分解，简化合并”。

算法步骤

• 分（Divide）：
  • 选择基准值（也称“主元”） (Pivot): 在待排序的数组或子数组中选择一个元素作为基准值（也称“主元”）。可以选择第一个元素、最后一个元素、中间元素或使用其他选择策略，如随机选择或“三数中值”法。
  • 划分 (Partition): 通过与基准值（也称“主元”）的比较，重新排列数组使得：基准值左边的所有元素都不大于它；基准值（也称“主元”）右边的所有元素都不小于它。
  • 经过这一步骤后，基准值（也称“主元”）将被放在其最终排序位置。
• 治（Conquer）：分别对基准值（也称“主元”）左、右两边的子数组递归地应用快速排序。
• 合（Merge）：对于快速排序，这一步实际上是不必要的。这是因为在“分”阶段中，数组或子数组已经被原地调整到了部分排序的状态。所以在治的步骤完成后，整个数组或子数组已经完全排序。换言之合的过程较为简单，只是将左右两个有序子数组合并上即可。
• 返回结果：返回合并结果，即为快速排序最终结果。
• 特殊说明：快速排序的关键点在于“分的过程”，因此在执行“分”的算法过程时，选择不同的基准值（这也是我在上述介绍基准值时，将其颜色加深的原因），会为整个算法带来不同的效率。具体情况后续会说明。

算法图示

分治

• 基本思想

  • 选择基准值：任选元素

    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/842830