快速排序(Quick Sort)是一种常用的排序算法,它的时间复杂度为 O(nlogn),是一种效率比较高的排序算法。但是快速排序不是稳定的排序算法。
稳定排序算法是指,如果排序前两个元素相对顺序相同,那么排序后它们的相对顺序仍然相同。而快速排序并不保证相同元素的顺序不发生改变,所以它不是稳定排序算法。
快速排序的最坏情况发生在每一次划分都只能分出一个元素的情况下,此时时间复杂度为 O(n^2),即和冒泡排序、插入排序等一样的复杂度。这种情况发生的原因通常是因为划分点选取不当,导致每次划分左右子序列的长度极度不平衡。为了避免这种情况,可以采用以下几种方法:
-
随机选取划分点:每次随机从待排序序列中选取一个元素作为划分点,从而降低最坏情况的概率。
-
三数取中法:选取待排序序列的第一个、中间一个、最后一个元素中的中间值作为划分点,从而降低最坏情况的概率。
-
在递归深度较浅时采用其他排序算法,比如插入排序或归并排序等,从而避免快速排序退化成 O(n^2) 的情况。
总的来说,快速排序不是稳定排序算法,但是它的效率比较高,可以通过一些方法来避免最坏情况。
标签:复杂度,划分,最坏,算法,排序,快速 From: https://www.cnblogs.com/xiao-longxia/p/17500780.html