美文网首页
双轴快排

双轴快排

作者: mrjunwang | 来源:发表于2018-10-11 14:49 被阅读0次

    Arrays.sort()
    双轴快排的基本原理是取两个pivot,所有比pivot1小的放到最左边,比pivot2
    * 大的放到最右边,然后递归下去,就可以把两端的元素完成排序,之后处理中间部分,中间部分如果过大就继续递归用这种方式继续分割,如果不大,就用单轴分割
    * 对两部分递归调用下去。
    算法步骤

    1.对于很小的数组(长度小于27),会使用插入排序。
    2.选择两个点P1,P2作为轴心,比如我们可以使用第一个元素和最后一个元素。
    3.P1必须比P2要小,否则将这两个元素交换,现在将整个数组分为四部分:
    (1)第一部分:比P1小的元素。
    (2)第二部分:比P1大但是比P2小的元素。
    (3)第三部分:比P2大的元素。
    (4)第四部分:尚未比较的部分。
    在开始比较前,除了轴点,其余元素几乎都在第四部分,直到比较完之后第四部分没有元素。
    4.从第四部分选出一个元素a[K],与两个轴心比较,然后放到第一二三部分中的一个。
    5.移动L,K,G指向。
    6.重复 4 5 步,直到第四部分没有元素。
    7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。
    8.递归的将第一二三部分排序。

    相关文章

      网友评论

          本文标题:双轴快排

          本文链接:https://www.haomeiwen.com/subject/qyebaftx.html