# 以上总结

![](https://3490195898-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LnQxDcxCKODvYvTUWe3%2F-Ly2q1OA_Hybo-NfT2I2%2F-Ly2taUdis_B0ji6wAU8%2Fimage.png?alt=media\&token=82364e6d-0d0c-4d1d-b436-5fbd5a56f60e)

如果不考虑稳定性，快排似乎是接近完美的一种方法，但可惜它是不稳定的。 那什么是稳定性呢？

通俗的讲**有两个相同的数A和B，在排序之前A在B的前面，而经过排序之后，B跑到了A的前面，对于这种情况的发生，我们管他叫做排序的不稳定性**，而快速排序在对存在相同数进行排序时就有可能发生这种情况。

{% hint style="info" %}
比如对(5，3A，6，3B ) 进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成 （3B，3A，5，6） 所以说快速排序是一个不稳定的排序
{% endhint %}

稳定性有什么意义？ 个人理解对于前端来说，比如我们熟知框架中的虚拟DOM的比较，我们对一个`<ul>`列表进行渲染，当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。

**辅助记忆**

* 时间复杂度记忆
  * 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)(一遍找元素O(n)，一遍找位置O(n)）
  * 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)(一遍找元素O(n)，一遍找位置O(logn))
* 稳定性记忆-“快希选堆”（快牺牲稳定性）

<br>