老刘1号

回复 15# 523066680


    哈哈，这和批处理倒是关系不大， 主要是用“只移动第一个元素”来模拟“交换任意两个元素”比较蛋疼

523066680

回复 16# 老刘1号

移动两个元素的同时还要保持其他元素的原有顺序，感觉好蛋疼

犯了一个数组坐标偏移计算错误，花了很多时间去矫正（就是临时数组消减后下标减小了，失算）

my @idx = qw/0 1 2 3 4/;
my ($a, $b) = (3,4);
my $apos = $a;
my $bpos = $b;
my $exchange = 0;
printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);

# 首位数插入idx[$b]的前方
$first = shift @idx;
splice( @idx, $b-1, 0, $first );
$apos-=1;
printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);

while (1)
{
    $first = shift @idx;
    if ( $first == $a ) {
        splice( @idx, $bpos, 0, $first );
        $apos = $bpos;
        $bpos -= 1;
        $exchange = 1;
    } else {
        if ( $bpos ne $a ) {
            if ($exchange) {
                splice( @idx, $apos-1, 0, $first );
                $bpos -= 1;
            } else {
                splice( @idx, $bpos-1, 0, $first );
                $apos -= 1;
            }
        } else {
            last;
        }
    }
    printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);
}
复制代码

前面两个数是位置变化

3 4, 0,1,2,3,4
2 4, 1,2,3,0,4
1 4, 2,3,0,1,4
0 4, 3,0,1,2,4
4 3, 0,1,2,4,3
复制代码

老刘1号

补一个冒泡排序

@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
Set /p List=
Set /A Steps=0
Call :冒泡排序算法 !List!
Call :Echo
Echo 第一个元素被移动的次数：!Steps!
Pause

:冒泡排序算法
	Call :GetList %*
	:Loop
		Set Flag=0
		For /l %%a in (2 1 !prt!) Do (
			Set /A SubOne=%%a-1
			Set /A #=.!SubOne!
			If !#! Gtr !.%%a! (
				Call :XChg !SubOne! %%a
				Set /A Flag=1
			)
		)
	If !Flag! Equ 1 Goto :Loop
Goto :Eof

:GetList
	Set /A Prt=0
	Set list=%*
	For %%a In (%*) Do (
		Set /A Prt+=1
		Set .!Prt!=%%a
	)
Goto :Eof

:XChg 两元素互换
	Rem 将需要互换的第一个元素换到第一位
	Set /A SubOne=%1-1
	For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
	Set /a Steps+=SubOne
	Rem 将需要互换的第一个元素塞到第二个元素后面
		Rem 计算新list中第二个元素的位置
		Set /A Arg2Index=%2-SubOne
		Rem 挪
		Call :MoveTo !Arg2Index!
		Set /a Steps+=1
	Rem 将需要互换的第二个元素换到第一位
	Set /a Arg2SubArg1SubOne=%2-%1-1
	For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
	Set /a Steps+=Arg2SubArg1SubOne
	Rem 将第二个元素塞到原先第一个元素的位置
		Rem 计算新list中第一个元素之前元素的位置
		Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
		Rem 挪
		Call :MoveTo !第一个元素之前元素的位置!
		Set /a Steps+=1
	Rem 还原其余各元素位置
	Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
	For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
	Set /a Steps+=Reserve
Goto :Eof

:MoveTo 移动到原先第%1个元素的后面
	Set /A #=.1
	For /l %%a in (1 1 %1) Do (
		Set /A PlusOne=%%a+1
		Set /A .%%a=.!PlusOne!
	)
	Set /A .%1=#
Goto :Eof

:Echo
	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
	Echo.
Goto :Eof
复制代码

7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：80
请按任意键继续. . .

老刘1号

选择排序

@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
Set /p List=
Set /A Steps=0
Call :选择排序算法 !List!
Call :Echo
Echo 第一个元素被移动的次数：!Steps!
Pause

:选择排序算法
	Call :GetList %*
	Set /A Count=0
	:Loop
		Set /A Count+=1
		Set /A #=.!Count!
		For /l %%a in (!Count! 1 !prt!) Do (
			If !.%%a! Leq !#! (
				Set /A #=.%%a
				Set /A Index=%%a
			)
		)
	If !Count! Neq !Index! Call :XChg !Count! !Index!
	If !Count! Lss !prt! Goto :Loop
Goto :Eof

:GetList
	Set /A Prt=0
	Set list=%*
	For %%a In (%*) Do (
		Set /A Prt+=1
		Set .!Prt!=%%a
	)
Goto :Eof

:XChg 两元素互换
	Rem 将需要互换的第一个元素换到第一位
	Set /A SubOne=%1-1
	For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
	Set /a Steps+=SubOne
	Rem 将需要互换的第一个元素塞到第二个元素后面
		Rem 计算新list中第二个元素的位置
		Set /A Arg2Index=%2-SubOne
		Rem 挪
		Call :MoveTo !Arg2Index!
		Set /a Steps+=1
	Rem 将需要互换的第二个元素换到第一位
	Set /a Arg2SubArg1SubOne=%2-%1-1
	For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
	Set /a Steps+=Arg2SubArg1SubOne
	Rem 将第二个元素塞到原先第一个元素的位置
		Rem 计算新list中第一个元素之前元素的位置
		Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
		Rem 挪
		Call :MoveTo !第一个元素之前元素的位置!
		Set /a Steps+=1
	Rem 还原其余各元素位置
	Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
	For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
	Set /a Steps+=Reserve
Goto :Eof

:MoveTo 移动到原先第%1个元素的后面
	Set /A #=.1
	For /l %%a in (1 1 %1) Do (
		Set /A PlusOne=%%a+1
		Set /A .%%a=.!PlusOne!
	)
	Set /A .%1=#
Goto :Eof

:Echo
	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
	Echo.
Goto :Eof
复制代码

7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：20
请按任意键继续. . .

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

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

523066680

回复 20# search_Sudoku

惊醒梦中人，我竟然没意识到到这个过程同样可以构建一个逐步扩大的有序列表, why didn't I think of that!
这样完全可以获得[步数]在[元素个数]以内的解，无论效率还是实现，应该都是最佳方案。

本来我在想那个递归跑出来的最短步骤解，但是想想就像通常情况下的的排序，某些解同样有更快的步骤，这些步骤的缩减有时只能是针对性的，即使实现了，也会改变效率的“天枰”。

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(表尾后部的两个元素是逆序的)

老刘1号

回复 17# 523066680


    学习了，又秒杀我那个无脑挪法……(固定挪表长+1次)
不知有没有最佳方案，明天再想想
论坛真是藏龙卧虎，不发点题都不肯出来

523066680

回复 24# 老刘1号

我先用递归跑出来一些结果，然后去强行找规律、强行解释一波，发现没什么大的漏洞就拿来用了。

有明确的调换方法，假设要调换列标3和7

012345678  -  将7和3位置调换，可以预见的是3和7调换后，012在7的前面（成为7的前缀）；456同理；
012345601278  - 将排头的012依次插入7的前方。
0003456012738 - 0127已经达成，现在开头的是数字3，将它放在数字7后面
0000456012745638 - 然后将前缀456插入数字3的前面。


有了这个规则，就可以来一波语法糖

my @index = qw/0 1 2 3 4 5 6 7 8/;
my ($a, $b) = (3,7);
my ($apos, $bpos) = ($a, $b);
my $show = sub {printf "[%d,%d] %s\n", $apos, $bpos, join(",", @index)};

$show->();
# $a 的前缀转移到 $b 前面
grep { splice( @index, $bpos-1, 0, shift @index ); $apos--; $show->() } (1..$a);

# $a 移到 $b 后面
splice( @index, $bpos, 0, shift @index );
$apos = $bpos, $bpos--;
$show->();

# $b 的前缀转移到 $a 前面
grep { splice( @index, $apos-1, 0, shift @index ); $bpos--; $show->() } ($a+1..$b-1);
exit;
复制代码

[3,7] 0,1,2,3,4,5,6,7,8
[2,7] 1,2,3,4,5,6,0,7,8
[1,7] 2,3,4,5,6,0,1,7,8
[0,7] 3,4,5,6,0,1,2,7,8
[7,6] 4,5,6,0,1,2,7,3,8
[7,5] 5,6,0,1,2,7,4,3,8
[7,4] 6,0,1,2,7,4,5,3,8
[7,3] 0,1,2,7,4,5,6,3,8
复制代码

.
回复 26# search_Sudoku

     针对 3,4,7,1,10,9,8,11,24（24暂时用K替代） 昨晚拿着扑克牌手动排了几次，处理方式和你的描述接近但有差异，
差不多7次。晚点儿再实践实践
    又想了想，递归也可以优化优化（暴力解虽然费时，但是省心 ）。

search_Sudoku

回复 21# 523066680

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

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

老刘1号

回复 22# search_Sudoku


    看懂了，谢大佬

老刘1号

回复 25# 523066680


    简单明了、高效，学习了。
我的思路（调换3与7）
12345678 - 不想太多，操作3与7就等到能操作的时候再操作，其他按顺序塞到后面
1234567812 - 此时所用步数记作step1
  345673812 - 3与7互换，∴先将3放到7后面
   45673812#456 - 继续无脑挪到7可操作，步数记为step2
      738127456 - 将7放到原先3的位置（4之前）
       3812745638 - 恢复原顺序，步数记为step3

由于一波操作下来除了3其它数字都移动一次，而3移动2次，∴总步数为表长+1
下面默认数组下标从1开始，
step1=%第一个数下标(3)%-1
step2=(%第二个数下标(7)%-%第一个数下标(3)%)-1
#一直固定在最开始第一个数(3)后面一个数(4)的前面
∴要计算第二个数(7)需要移动到的位置，就计算"最开始第一个数后面的一个数(4)“的位置。
由于前面每次移动都必然会移动到4的后面，∴4的新下标=4的原下标-步数+表长=(3的原下标+1)-(step1+1+step2)+表长
∴第二个数(7)需要移动到”4的新下标-1“这个下标代表的数的后面，即"(3的原下标+1)-(step1+1+step2)+表长-1"
step3=总步数-已走步数=(表长+1)-(step1+1+step2+1)

真蛋疼

523066680

回复 22# search_Sudoku

      按这个方式实现了（二分搜索没做进去），很利落

=info
    Ref:
    http://www.bathome.net/redirect.php?goto=findpost&ptid=51910&pid=217048
=cut

my @arr = qw/25 23 4 9 8 2 1 12 15/;
my $offset;
my $first;
printf "%s <- Original\n", join(",", @arr);

# 查找末尾有序数组的起点
$offset = $#arr+1 - seqsizes( \@arr );

while ( $offset > 0 || $arr[0] > $arr[1] )
{
    $first = shift @arr;
    insert( \@arr, $offset, $first );
    $offset--;
    printf "%s\n", join(",", @arr);
}

sub insert
{
    my ($arr, $begin, $ele) = @_;
    for my $i ( $begin .. $#$arr ) {
        if ($arr->[$i] > $ele ) { splice( @$arr, $i, 0, $ele ); return; }
    }
    splice( @$arr, $#$arr+1, 0, $ele );
}

sub seqsizes
{
    my ($r, $size) = (shift, 1);
    for my $i (1..$#$r) {
        $r->[-$i] > $r->[-$i-1] ? $size++ : last;
    }
    return $size;
}
复制代码

3,4,7,1,10,9,8,11,24 <- Original
4,7,1,10,9,3,8,11,24
7,1,10,9,3,4,8,11,24
1,10,9,3,4,7,8,11,24
10,9,1,3,4,7,8,11,24
9,1,3,4,7,8,10,11,24
1,3,4,7,8,9,10,11,24
复制代码

25,23,4,9,8,2,1,12,15 <- Original
23,4,9,8,2,1,12,15,25
4,9,8,2,1,12,15,23,25
9,8,2,1,4,12,15,23,25
8,2,1,4,9,12,15,23,25
2,1,4,8,9,12,15,23,25
1,2,4,8,9,12,15,23,25
复制代码

老刘1号

回复 22# search_Sudoku


    用批实现一个，带二分的之后补上，
在表尾构建有序数列（非二分检索，倒序检索）.BAT

@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
Set /p List=
Call :GetList !List!
Set /A 判断次数=0,挪移次数=0

Rem 确定末尾有序数组的起始位置
Set /A point=prt-1
For /l %%a in (!prt! -1 2) Do (
	Set /A SubOne=%%a-1
	Set /A #=.!SubOne!
	Set /A 判断次数+=1
	If !#! Gtr !.%%a! (
		Set /A Point=SubOne
		Goto :JmpOut1
	)
)
:JmpOut1

Rem 挪
For /l %%a in (!Point! -1 1) Do Call :挪 %%a
Goto :Next
	:挪
	For /l %%b in (!prt! -1 %1) Do (
		Set /A 判断次数+=1
		If !.1! Gtr !.%%b! (
			Call :MoveTo %%b
			Set /a 挪移次数+=1
			Set/p=移到%%b后：<nul
			Call :Echo
			Goto :JmpOut2
		)
	)
	:JmpOut2
	Rem 处理首个元素比末尾有序数组全小的情况
	Set /A 判断次数+=1
	If !.1! Lss !.%1! (
		Call :MoveTo %1
		Set /a 挪移次数+=1
		Set/p=移到%1后：<nul
		Call :Echo
	)
	Goto :Eof
:Next

Set 判断次数
Set 挪移次数
pause&"%~0"

:GetList
	Set /A Prt=0
	Set list=%*
	For %%a In (%*) Do (
		Set /A Prt+=1
		Set .!Prt!=%%a
	)
Goto :Eof

:MoveTo 移动到原先第%1项的后面
	Set /A #=.1
	For /l %%a in (1 1 %1) Do (
		Set /A PlusOne=%%a+1
		Set /A .%%a=.!PlusOne!
	)
	Set /A .%1=#
Goto :Eof

:Echo
	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
	Echo.
Goto :Eof
复制代码

1 3 5 2 4
移到3后：3-5-1-2-4-
移到4后：5-1-2-3-4-
移到5后：1-2-3-4-5-
判断次数=11
挪移次数=3
请按任意键继续. . .

7 3 4 1 10 9 8 11 24
移到6后：3-4-1-10-9-7-8-11-24-
移到5后：4-1-10-9-3-7-8-11-24-
移到5后：1-10-9-3-4-7-8-11-24-
移到4后：10-9-3-1-4-7-8-11-24-
移到7后：9-3-1-4-7-8-10-11-24-
移到6后：3-1-4-7-8-9-10-11-24-
移到2后：1-3-4-7-8-9-10-11-24-
判断次数=38
挪移次数=7
请按任意键继续. . .

25 23 4 9 8 2 1 12 15
移到9后：23-4-9-8-2-1-12-15-25-
移到8后：4-9-8-2-1-12-15-23-25-
移到5后：9-8-2-1-4-12-15-23-25-
移到5后：8-2-1-4-9-12-15-23-25-
移到4后：2-1-4-8-9-12-15-23-25-
移到2后：1-2-4-8-9-12-15-23-25-
判断次数=36
挪移次数=6
请按任意键继续. . .