快速排序（Quicksort），又称分区交换排序，是一种基于分治思想的高效原地排序算法，由 Tony Hoare 于 1959 年提出。其工作原理是从数组中选取一个“基准”（pivot）元素，再根据其余元素是小于还是大于基准，把它们划分到两个子数组中，然后对子数组递归排序。这一过程持续进行，直至达到基准情形——数组或子数组包含零个或一个元素，此时已然有序。如果所选基准恰好是数组中的最小或最大元素，快速排序的最坏情况性能会退化为 O(n^2)，不过当基准随机选取时这种情况很少发生。其平均情况时间复杂度为 O(n log n)。