数据结构浙江大学整理（2）

10.2 表排序

10.2.1 算法概述

表排序用于：元素不是简简单单的排序，每一个元素都是一个庞大的结构，例如一个结构体等，此时如果我们想要交换两个元素，就不能忽略交换所需要的时间了。表排序就是在移动的时候，并不移动原始的数据，只是移动指向它的指针。

它是一种间接排序的方法，定义一个指针数组作为“表”（table）。

用下面一个例子来举例：

利用插入算法，可以得出：

如果仅要求按顺序输出，则输出：

A[table[0]],A[table[1]],……,A[table[N-1]]

10.2.2 物理排序

所谓物理排序就是说，我们不能像前文那样利用指针来移动，而是必须实际移动结构体，那该怎么办呢？

利用这样一个原理：N个数字的排列由若干个独立的环组成。

为了解释这个原理，看10.2.1中最后的结果那个表，table[0]值（3）->table[3]值（1）->table[1]的值（5）->table[5](0)返回到了table[0]。一共有三种环，这三种环互不相交，称为独立。

在排序的时候，先对一个环内进行排序。那么如何判断一个环的结束呢？

每访问一个空位i后，就令table[i]=i。当发现table[i]==i时，环就结束了。

下面分析一下复杂度的情况：

（1）最好的情况：初始即有序。

（2）最坏的情况：有N/2个环，每个环包含两个元素，元素需要移动3N/2次。

但是无论如何，复杂度都可以写为T(N)=O(mN)，其中m是每个A元素复制需要的时间。