快速排序

排序算法

快速排序是一种高效的分治算法,通过选择一个基准元素,将数组分为两部分,一部分小于基准,一部分大于基准,然后递归地对两部分进行排序。

时间复杂度:最佳 O(n log n) | 平均 O(n log n) | 最差 O(n²)
空间复杂度:O(log n)
稳定性:不稳定

应用场景/前提条件

  • 实际应用中最常用的高效排序算法
  • 对于大多数输入可达到最佳性能
  • 缓存友好

算法讲解

介绍

快速排序(Quick Sort)是一种极其高效的分治排序算法,也是实际应用中最常用的排序算法之一。

它的核心思想可以概括为“选个基准,然后左右站队”:

  1. 选基准(pivot):首先,从数组中任意选择一个元素作为“基准”。
  2. 站队:接着,重新排列数组,将所有小于基准的元素移动到基准的左边,所有大于等于基准的元素移动到右边。这一步完成后,该基准元素就找到了它在最终有序序列中的“最终位置”。
  3. 分而治之:最后,对基准左右两边的子数组(现在它们是两个独立的、更小的问题),递归地重复上述过程,直到每个子数组都排序完毕。

通过这种巧妙的“分而治之”策略,快速排序能将一个大问题不断分解成小问题来解决,平均时间复杂度能达到卓越的 O(nlogn)。

算法步骤

  1. 从数列中选择一个元素作为"基准",本文采用最左侧元素作为基准
  2. 将所有比基准值小的元素放到基准前面,所有比基准值大的元素放到基准后面(分区操作)
  3. 对基准左右两个子序列分别重复步骤1和2,直到子序列只有一个元素或为空

核心特性

  • 分治策略:将问题分解为更小的子问题,逐步解决

...