search_Sudoku

1 3 5 2 4
3 5 2 1 4
5 2 1 3 4
2 1 3 4 5
1 2 3 4 5

第 1 次 对 首元素 在 表后部 长度为 1 的子表中 检索(二分法) 找到 应插入的位置
第 2 次 对 首元素 在 表后部 长度为 2 的子表中 检索(二分法) 找到 应插入的位置
第 3 次 对 首元素 在 表后部 长度为 3 的子表中 检索(二分法) 找到 应插入的位置
第 4 次 对 首元素 在 表后部 长度为 4 的子表中 检索(二分法) 找到 应插入的位置
第 5 次 对 首元素 在 表后部 长度为 5 的子表中 检索(二分法) 找到 应插入的位置
...     对
第 i 次 对 首元素 在 表后部 长度为 i 的子表中 检索(二分法) 找到 应插入的位置


要排序的表元素为 n 个, 移动插入的总次数在最差情况下为 n

优化算法在于最优化检索算法, 比如用二分检索

search_Sudoku

回复 21# 523066680


子表 的起始长度 可以不从 1 开始, 而是找出当前表后部的最长有序子表, 这样可以减少插入的次数,

对 m 个元素的表 T 排序, 找出表尾的最大有序子表 Ts, 此子表长度为 n, 那么只需要且至少需要 m-n 次移动完成排序

将原表表示如下, 括号内为下标序号
E(1), E(2), E(3), ...., X, E(m-n+1), E(m-n+2), E(m-n+3),..., E(m)

X 的序号是 m-n, X 和 E(m-n+1) 是逆序的

E(m-n+1), E(m-n+2), E(m-n+3),..., E(m) 是一个已经达成目标序的最大有序子表

每一次移动操作如果是把首位置元素移动插入到 Ts, 将使 Ts 的长度增 1, 将只需要 m-n 次移动插入即完成排序

如果有任何一次插入目标位置是在 X 的位置之前, 将不可能减少1次插入次数, 因为 X 必须在前面所有元素都移动之后才能移动, 而且 X 也必须移动才能使全表有序(因为 X 在移动之前至少有一个后面位置的元素与其形成逆序关系).

如果有任何一次把元素 Y 插入到目标位置是在 X 相邻的后一位置, 但没有和后面的 Ts 构成一个更大的有序子表, 换言之, 即 Y 与 相邻的后一位置的元素仍是逆序关系, 也一样不能减少 1 次插入次数, 设 Y 移动之前 Ts 的长度已经增长到 L, 那么还至少需要 m-L 次移动插入才能完成排序, 而 Y 的移动并没有增长 Ts 的长度, 那么其移动插入之后, 就一样至少需要 m-L 次移动插入才能完成排序.

综上, 结论: 对 m 个元素的表 T 排序, 找出表尾的最大有序子表 Ts, 此子表长度为 n, 那么只需要且至少需要 m-n 次移动完成排序

算法在开始从表尾向前面逐次对相邻2元素比较, 直到出现逆序, 以此确定表尾的最大长度有序子表, 之后再进行 m-n 次检索移动插入的操作完成全表排序

search_Sudoku

回复 21# 523066680

不同的排序算法自然不能以最好情况下的效率做比较, 而是要以平均效率做比较

我思考这个算法的过程是逆推的:

假设原表T (长度为 L)已是完全有序的, 需要插入的次数是 0

如果不是完全有序的, 就至少要做一次插入操作

在最后一次插入时, 表后部的 长度为 L-1 的子表必然已经是一个完全有序的表(设这个表为T1)

如果 T1 也是由插入操作之后得到的, 那么 去除 那个 插入进来(插入位置包括最前部和最尾部)的元素, 长度为 L-2 的子表 T2 必然也是一个完全有序表,

...

逆推到第一次插入之前, 必然在全表后部存在一个完全有序表, 这个完全有序子表最大长度为 L (也就是全表本来就是完全有序的), 最小长度是 1(表尾后部的两个元素是逆序的)

search_Sudoku

回复 21# 523066680

http://www.bathome.net/redirect. ... 1910&pid=217050

22楼, 我做了一个不太严谨的证明