Physical Sort

发表于 更新于 分类于

  物理排序...

物理排序

  • 我们从上一节的知识开始 表排序，在某些需求下，我们需要实在的交换表中元素的物理地址，不能通过一张额外的table来达到我们的目的。物理排序可以到达我们的要求
  • 排序完成的结果如下，并且这个排序结果必然有若干个相互独立的环组成
A A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
Key f d c a g b h e i u
table 0 1 2 3 4 5 6 7 8 9
环 3 5 2 1 7 0 4 6 8 9

  • 我们从table[0]= 3 开始,我们从不同的环的任意一个元素开始切入，遍历元素，最后我们都将回到这个元素，这就是环

    1
    2
    // table[0] -> table[3] -> table[1] -> table[0]
    // 上述序列构成了一个环

  • 排序，按环处理：

    • 首先，取一个临时变量temp随机存储，环中的任意一个元素，以A[0]为例：

      1
      temp  = f;  // 此时A[0] 为空

    • 将table中的元素放到A[0],A[0] = A[table[0]];

    • A A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
      Key f d c a g b h e i u
      table 0 1 2 3 4 5 6 7 8 9
      环 3 5 1 0
      new key a null
      table 0 1
      new key a null d
      table 0 5 3
      new key a b d null
      table 0 1 3 0
      new key a b d f
      table 0 1 3 5

    • 判断环结束：

      • table[i] == i，此时环结束

  • 复杂度分析：

    • 最好： 初始的时候都有序
    • 最坏：两本书(a,b)发生交换，需要三个步骤：
      • 两本书发生交换：
        • 取出一本(a)，temp
        • a = b;
        • b = temp;
      • 存在[N/2]个环，每个环两个元素，需要[3N/2]此移动
    • T = O(mN),m是每个元素A的复制时间