基本思想
当数组中含有大量重复的元素,则partition函数可能把数组分成不平衡的两部分,时间复杂度退化成O(n²)。这时候应该把小于v和大于v放在数组两端
时间和空间复杂度同快速排序。 有大量重复元素的数组使用快速排序效率是非常低的,导致 子数组不平衡,甚至会退化成 O(n*2) 的算法,这时可以用双路快速排序算法进行优化。
当数组中含有大量重复的元素,则partition函数可能把数组分成不平衡的两部分,时间复杂度退化成O(n²)。这时候应该把小于v和大于v放在数组两端
时间和空间复杂度同快速排序。 有大量重复元素的数组使用快速排序效率是非常低的,导致 子数组不平衡,甚至会退化成 O(n*2) 的算法,这时可以用双路快速排序算法进行优化。
本文标题:双路快速排序(有空再完善吧)
本文链接:https://www.haomeiwen.com/subject/imyamltx.html
网友评论