快速排序

快速排序，也称为分区交换排序，是一种高效的、原地的排序算法，它使用了分治原则。它由 Tony Hoare 于 1959 年开发。其工作原理是从数组中选择一个“基准”元素，并将其他元素根据是否小于或大于该基准划分为两个子数组。然后递归地对这两个子数组进行排序。这个过程一直持续，直到达到基本情况，即数组或子数组包含零个或一个元素，因此已经是有序的。如果基准是数组中最小或最大的元素，快速排序的最坏情况性能为 O(n^2)，尽管如果随机选择基准，这种情况很少见。平均情况的时间复杂度为 O(n log n)。