快速排序——分治的表弟

配套视频：快速排序——分治的表弟_哔哩哔哩_bilibili

主要思想：

(资料图片)

快速排序是一种基于分治法的排序算法，它的思想就在于找一个“基准”。 快速排序通过选择一个基准元素，然后将数组分为小于基准元素和大于基准元素的两个子数组。接下来，对这两个子数组再次进行快速排序，一直这样分下去，直到被排序的数组只剩两个元素，结果就显而易见了。快速排序的核心在于如何选择基准元素以及如何将数组进行划分。一般来说，可以随意选择数组的元素作为基准元素。然后，通过比较其他元素与基准元素的大小，将它们划分到相应的子数组中。这个过程称为划分操作。

两个指针一起工作是将大问题一分为二的其中一个方法，在现实中，不一定要两个指针，也可以用其他方法。在这个方法中，其中的两个指针一个指向基准，一个指向和基准作比较的数，常用left（左）和right（右）来命名。

由于快速排序是递归的，最坏情况发生在选择的基准元素总是最小或者最大的元素。为了避免最坏情况，可以采用随机选择基准元素的方法，出现最坏元素的几率也就减少了。

适用范围：

快速排序适用于需排序的场景，并且原数组能够分解成若干个子数组，并且子数组可以用相同的方法继续划分下去，直到结果变得显而易见为止。 

例题：

总结：

总结一下，快速排序是基于分治法的排序算法，它通过选择一个基准元素并将数组划分为两个子数组来进行排序。快速排序具有很快的速度，并且是原地排序算法，不需要多余空间。然而，快速排序的最坏情况下将不再快速，很缓慢，所以需要注意避免最坏情况的发生。

快速排序是一种高效的排序算法，通过选取基准元素和划分过程将序列不断分割成更小的子序列，并对子序列进行递归排序，最终完成整个序列的排序。在实际应用中，快速排序被广泛使用。他又称“双指针法”，使用了两个指针，一个指向基准，一个指向和基准比对的数。

快速排序步骤大致分为“选取基准元素”、“划分”和“递归排序”三大步。

好啦，关于动态规划就说到这里。这里是康郭聊算法，拜拜！

#注：例题答案请查看视频。