快速排序原理,及为何使用

发布时间 2023-12-04 22:23:32作者: 纯粹的

1.原理

对于每一次函数调用,选当前数组的第一个元素为标准值,遍历数组,把所有小于标准值的元素放到标准元素的左边,大于等于标准值的元素放到右边。知道调用函数中的数组长度小于2。

2.为何使用

**1).**虽然时间复杂度不稳定->(O2),但是在许多应用场景中,我们并不需要稳定性。
**2).**没有病态的比较,即当a<b,b<c时,若再对a和c进行比较,就叫做病态的比较,显然对快速排序,病态比较不会发生。
**3).**空间复杂度小,快速排序是原地排序(python实现还蛮简单的,C语言?)