快速排序算法

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

首先，选择一个元素作为基准（pivot），通常选择序列的第一个或最后一个元素。接着，将所有小于基准的元素移动到基准的左侧，大于基准的元素移动到右侧。这个过程称为分区操作。分区完成后，基准元素就位于其最终的正确位置上。然后对基准左右两侧的子序列重复上述过程，直到整个序列有序。

快速排序的时间复杂度平均为O(n log n)，但在最坏的情况下（如序列已经完全有序时）时间复杂度会退化到O(n^2)。为了优化性能，可以选择随机化选择基准或者使用三数取中法来选择基准，从而减少最坏情况出现的概率。

快速排序因其简洁性和高效性，在实际应用中非常广泛，特别是在大数据量处理中表现出色。