原地哈希Hash算法——O(n)线性时间复杂度排序打乱的1~n数列

问题

给定一个排列：

\mathrm{P}_n = \{ p_1, p_2, \cdots,p_n \}

满足对于任意1到n的正整数x，都一定能找到p_i = x。即排列\mathrm{P}_n是\{1,2, \cdots,n\}的全排列中的一种。

我们希望对该排列排序。要求：

• 不使用额外数组
• 只能在原数组上修改
• 时间复杂度是线性的\Theta (n)

原地哈希法

从前到后遍历1到n，对于第i个数，如果我们发现a[i] \neq i，那么就交换a[i]和a[a[i]]。C/C++代码如下：

for (int i = 1; i <= n; ++i)
{
    if (a[i] != i)
        swap(a[i], a[a[i]]);
}

我们可以发现该算法的时间复杂度是显然的线性\Theta (n)。每次操作都至少能使得a[a[i]]是正确的，且每次操作不会改变已经在正确位置上的数，而由于排列中的数恰好取遍1~n，故所有位置都可以正确排列。