【数据结构笔记37】表排序与物理排序

本次笔记内容：
10.2.1 算法概述
10.2.2 物理排序

表排序情况

待排元素不是一个简单的整数，而是一个庞大的结构体，因此移动元素的时间不能忽略不计。

表排序算法概述

间接排序：定义一个指针数组作为“表”（table）。

如上图，只需要定一个table，进行相关排序即可；无需移动元素位置。

物理排序

如上图，N个数字的排列由若干个独立的环组成。

即：

• A[0]对应table[3]，A[3]对应table[1],A[1]对应table[5]，A[5]对应table[0]，这是一个环。
• 有了独立的环，针对每个环进行移动操作则减少移动次数（避免无效的移动）。
• 首先将A[0]存在Temp，之后将A[3]移至[0]，则此时[3]处空出，将A[1]移至[3]，以此类推。

应该如何判断一个环结束呢？

• if(table[i] == i) break;
• 每当放好一本书时，就把其所放位置table[i]设为i。

复杂度分析

最好情况：初始即有序；
最坏情况：

• 有$\lfloor N/2 \rfloor$⌊N/2⌋个环，每个环包含2个元素；
• 需要$\lfloor 3N / 2 \rfloor$⌊3N/2⌋此元素移动。
• 则$T=O(mN)$T=O(mN)，m是每个A元素的复制时间。