视频字幕
快速排序是计算机科学中最重要的排序算法之一。它采用分治策略,首先选择一个基准元素,然后将数组重新排列,使得所有小于基准的元素都在基准左边,大于基准的元素都在基准右边。
分区是快速排序的核心步骤。我们选择第一个元素8作为基准,然后设置左右两个指针。左指针从第二个元素开始向右移动,寻找大于基准的元素。右指针从最后一个元素开始向左移动,寻找小于基准的元素。当找到这样的元素对时,就交换它们的位置。
经过分区过程,我们成功地将数组重新排列。所有小于基准8的元素都移到了左边,基准元素8现在位于它在最终排序中的正确位置。左边的子数组包含所有小于8的元素,现在我们需要对这个子数组递归地应用快速排序。
快速排序的递归过程是算法的精髓。对左子数组继续应用快速排序,选择新的基准元素,重复分区过程。每次递归都会将问题规模减小,直到子数组的长度小于等于1时,递归结束。最终,所有的子数组都被正确排序,整个数组就变成了有序状态。
快速排序的时间复杂度分析很重要。在最好和平均情况下,时间复杂度为O(n log n),这使得它成为最高效的排序算法之一。但在最坏情况下,比如数组已经有序时,时间复杂度会退化到O(n²)。空间复杂度平均为O(log n),主要来自递归调用栈。尽管如此,快速排序因其优秀的平均性能和原地排序特性,在实际应用中非常广泛。