示例:[[1,5],[2,7],[,10,18],[,17,19]] 结果:[[1,7],[10,19]] 为什么呢?...快速排序
快速排序核心原理是经过一趟排序之后,使得这一组数据在某个值左边全是小于这个值的,在这个值的右边全是大于这个值的,然后递归排序左边的数组和右边数组,直到最后数组的大小是1,排序终止,如下图,
?...快速排序使用了递归算法,每次分区之后,数组都会被切分成两个大小差不多相等的小区间,直到区间大小为1,这个过程需要log(n)次,每个区间进行排序需要遍历n(数组的结尾-开始)次,所以时间复杂度是nlog...(n),极端情况下会退化成n2,例如[1,2,3,4,5],这种情况下,数组是有序的,假设我们选的分区值是1,每次分区后两个数组的大小差距太大(数组长度-2),,所以需要执行n次分区操作,那么时间复杂度会退化成...,分区时分区的值选取也很关键,一般采用中位数
快速排序的平均时间复杂度是nlog(n),其退化到n2的概率是非常小的,我们也可以选取合适的中间值进行避免,但他的原地排序,分治思想是非常优秀的,所以他在实际场景中应用广泛