视频字幕
快速排序是计算机科学中最重要的排序算法之一。它采用分治策略，通过选择一个基准元素，将数组分为两个子数组，然后递归地对子数组进行排序。快速排序的平均时间复杂度为O(n log n)，在实际应用中表现优异。
分区操作是快速排序的关键步骤。首先选择一个基准元素，通常选择数组的最后一个元素。然后遍历数组，将小于基准的元素移到左边，大于基准的元素移到右边。最后将基准元素放到正确的位置。在这个例子中，基准是90，所有其他元素都小于90，所以都被放在左边。
快速排序通过递归来完成排序过程。在分区操作后，我们得到了左子数组和右子数组。然后对这两个子数组分别进行递归排序。基准元素已经在正确的位置，不需要移动。这个过程会一直递归下去，直到子数组的大小为1或0。快速排序的平均时间复杂度是O(n log n)，但在最坏情况下会退化到O(n²)。
这是快速排序的Python实现代码。主函数quick_sort负责递归调用，当low小于high时继续分区。partition函数是核心，它选择最后一个元素作为基准，通过双指针技术将数组重新排列。代码中的交换操作确保小于基准的元素都在左边。整个算法的平均时间复杂度是O(n log n)，空间复杂度是O(log n)，主要用于递归调用栈。
快速排序有多种优化策略来提升性能。三数取中法可以避免最坏情况，对小数组使用插入排序能减少递归开销，随机化基准选择也能改善平均性能。快速排序广泛应用于大规模数据排序、数据库索引构建等场景。与其他排序算法相比，快速排序平均性能优秀且是原地排序，但需要注意它是不稳定排序，最坏情况下时间复杂度会退化到O(n²)。