1.原理
对于每一次函数调用,选当前数组的第一个元素为标准值,遍历数组,把所有小于标准值的元素放到标准元素的左边,大于等于标准值的元素放到右边。知道调用函数中的数组长度小于2。
2.为何使用
1).虽然时间复杂度不稳定->(O2),但是在许多应用场景中,我们并不需要稳定性。
2).没有病态的比较,即当a<b,b<c时,若再对a和c进行比较,就叫做病态的比较,显然对快速排序,病态比较不会发生。
3).空间复杂度小,快速排序是原地排序(python实现还蛮简单的,C语言?)
对于每一次函数调用,选当前数组的第一个元素为标准值,遍历数组,把所有小于标准值的元素放到标准元素的左边,大于等于标准值的元素放到右边。知道调用函数中的数组长度小于2。
1).虽然时间复杂度不稳定->(O2),但是在许多应用场景中,我们并不需要稳定性。
2).没有病态的比较,即当a<b,b<c时,若再对a和c进行比较,就叫做病态的比较,显然对快速排序,病态比较不会发生。
3).空间复杂度小,快速排序是原地排序(python实现还蛮简单的,C语言?)