一个有限制的排序算法题(页 1) - 出题挑战 - 批处理之家 BAT,CMD,批处理,PowerShell,VBS,DOS

老刘1号 发表于 2019-1-22 12:17

一个有限制的排序算法题

昨天群里看到的，
[quote]【吐槽】Tiger<haotian.fan@qq.com> 下午 2:09:55
网上看见一道题目，问下大家，
如果一个List只能移动第一项，请问如何排序？
【中华】zhonghua(1138520994) 下午 3:02:33
@Tiger Tiger 只能移动第一项是啥意思，栈之类的结构么
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:02:56
就比如说 5 1 3 2 4只能移动5，不能移动其他元素
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:03:11
stack overflow看到的，有点解不开
【中华】zhonghua(1138520994) 下午 3:04:28
这个移动是啥意思
pop（0）？
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:04:54
比如说移到3后面就编程1 3 5 2 4[/quote]
我的解法(伪插入排序，效率底下，各位大佬见笑)：[code]@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
Set /p List=
Call :GetList !List!
Set /A Count=1
:Loop 首项逆向比较
Set /A Flag1=0
For /l %%a in (!prt! -1 1) Do (
If !.1! Gtr !.%%a! (
Call :MoveTo %%a
Set /A Flag1=1
Goto :JmpOut
)
)
:JmpOut
If !Flag1! Equ 1 Goto Loop
Set /A Count+=1
If !Count! Leq !prt! (
Call :MoveTo !Count!
Goto :Loop
)
For /l %%a in (1 1 !prt!) Do Set .%%a
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[/code]

523066680 发表于 2019-1-22 12:34

[i=s] 本帖最后由 523066680 于 2019-1-22 12:44 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217027&ptid=51910]1#[/url] [i]老刘1号[/i] [/b]

问题1，只有首个元素可以移动，他可以移动到任意位置吗
若按C数组操作，如果你可以移动到中间位置，那不是还等于其他元素也可以移动了
问题2，想看stackoverflow原帖，也许是leetcode上面的题目？

老刘1号 发表于 2019-1-22 12:52

[i=s] 本帖最后由老刘1号于 2019-1-24 13:06 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217028&ptid=51910]2#[/url] [i]523066680[/i] [/b]

刚去拷问了一波问主，原话
[quote]每次移动完以后，只能移动第一个，插入以后，列表开头就是新的可移动元素[/quote]

523066680 发表于 2019-1-22 12:57

[i=s] 本帖最后由 523066680 于 2019-1-22 13:13 编辑 [/i]

int a[5] = {a,b,c,d,e} 把数组变成 {b,c,a,d,e}
b和c 不是从 1,2的位置变成了 0,1的位置吗。（这种允许的话，感觉跟打牌手法的插入排序差不多。）

除非说这是一个定制的数据结构，每个数之间有足够的间隙，开头的数字可以插入任意数字中间而其他数字不需要移动。
比如 a,,,,b,,,,c,,,,d,,,,e,,,,

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217031&ptid=51910]5#[/url] [i]老刘1号[/i] [/b]
不纠结数据结构，纠结的是描述。觉得你现在的描述就比较合理了，其他数字被动移动。

老刘1号 发表于 2019-1-22 13:10

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217030&ptid=51910]4#[/url] [i]523066680[/i] [/b]

总觉得不需要纠结结构……
我觉得问主的意思就是，第一个随意移动，其余的被动移动，顺便改变位置

老刘1号 发表于 2019-1-22 13:29

补一个优化版[code]@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
Set /p List=
Call :GetList !List!
Set /A Count=1
:Loop
Rem 首项逆向比较
Set /A Flag1=0
For /l %%a in (!prt! -1 1) Do (
If !.1! Gtr !.%%a! (
Call :MoveTo %%a
set/p=移动到%%a后：<nul
For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
Echo.
Set /A Flag1=1
Goto :JmpOut
)
)
:JmpOut
If !Flag1! Equ 1 Goto Loop

Rem 判断是否排序完成。
Set /A Flag2=0
For /l %%a in (1 1 !prt!) Do (
Set /A PlusOne=%%a+1
Set /A "#=.!PlusOne!"
If !#! Lss !.%%a! (
Set Flag2=1
If %%a equ !prt! Set Flag2=0
Goto :JmpOut2
)
)
:JmpOut2
If !Flag2! Equ 0 Goto End

Rem 继续排序
Set /A Count+=1
If !Count! Leq !prt! (
Call :MoveTo !Count!
Set/p=移动到!Count!后：<nul
For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
Echo.
Goto :Loop
)
:End
For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
Echo.&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[/code][code]5 1 3 2 4
移动到5后：1-3-2-4-5-
移动到2后：3-1-2-4-5-
移动到3后：1-2-3-4-5-
1-2-3-4-5-
请按任意键继续. . .
3 2 1
移动到3后：2-1-3-
移动到2后：1-2-3-
1-2-3-
请按任意键继续. . .
7 3 4 1 10 9 8 11 24
移动到4后：3-4-1-7-10-9-8-11-24-
移动到3后：4-1-3-7-10-9-8-11-24-
移动到3后：1-3-4-7-10-9-8-11-24-
移动到2后：3-1-4-7-10-9-8-11-24-
移动到2后：1-3-4-7-10-9-8-11-24-
移动到3后：3-4-1-7-10-9-8-11-24-
移动到3后：4-1-3-7-10-9-8-11-24-
移动到3后：1-3-4-7-10-9-8-11-24-
移动到4后：3-4-7-1-10-9-8-11-24-
移动到4后：4-7-1-3-10-9-8-11-24-
移动到4后：7-1-3-4-10-9-8-11-24-
移动到4后：1-3-4-7-10-9-8-11-24-
移动到5后：3-4-7-10-1-9-8-11-24-
移动到5后：4-7-10-1-3-9-8-11-24-
移动到5后：7-10-1-3-4-9-8-11-24-
移动到5后：10-1-3-4-7-9-8-11-24-
移动到7后：1-3-4-7-9-8-10-11-24-
移动到6后：3-4-7-9-8-1-10-11-24-
移动到6后：4-7-9-8-1-3-10-11-24-
移动到6后：7-9-8-1-3-4-10-11-24-
移动到6后：9-8-1-3-4-7-10-11-24-
移动到6后：8-1-3-4-7-9-10-11-24-
移动到5后：1-3-4-7-8-9-10-11-24-
1-3-4-7-8-9-10-11-24-
请按任意键继续. . .
1 2 3 5 4
移动到2后：2-1-3-5-4-
移动到2后：1-2-3-5-4-
移动到3后：2-3-1-5-4-
移动到3后：3-1-2-5-4-
移动到3后：1-2-3-5-4-
移动到4后：2-3-5-1-4-
移动到4后：3-5-1-2-4-
移动到4后：5-1-2-3-4-
移动到5后：1-2-3-4-5-
1-2-3-4-5-
请按任意键继续. . .[/code]

523066680 发表于 2019-1-22 13:49

[i=s] 本帖最后由 523066680 于 2019-1-22 15:13 编辑 [/i]

有缺陷/未完成，大概方向，unshift 取出首个数字，和剩下的各个元素做减法，找出相差距离最近的数字（分为L和R）的对应坐标，插入。可能做足判断会好一些，待完善。[code]my @arr = qw/5 1 9 3 2 4 6/;
my ($first, $L,$R,$r_id, $l_id, $dt);
my $max = 100000;

for (1..5)
{
$first = shift @arr;
$L = -$max;
$R = $max;
$r_id = 0;
$l_id = 0;
for $i ( 0 .. $#arr ) {
      $dt = $arr[$i] - $first;
      if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }
      if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }
}

if ( $R == $max ) {
      push @arr, $first;
} else {
      splice( @arr, $r_id, 0, $first );
}
#printf "%d - %d: %d, %d: %d\n", $first, $l_id, $L, $r_id, $R;
print join(",", @arr), "\n";
}

#print join("", @arr);
[/code]1,9,3,2,4,5,6
9,3,1,2,4,5,6
3,1,2,4,5,6,9
1,2,3,4,5,6,9

特地找一副扑克牌玩了一下，为啥人玩起来就这么自然…… 转成代码总是有纰漏，
纠正了某些情况下不能完全处理的问题，也未经过严格验证，暂时这样。[code]my @arr = qw/7 3 4 1 10 9 8 11 24/;
my ($first, $L,$R,$r_id, $l_id, $dt);
my $max = 100000;
my $ok = 0;

while (1)
{
$first = shift @arr;
$L = -$max;
$R = $max;
$r_id = 0;
$l_id = 0;
for $i ( 0 .. $#arr ) {
      $dt = $arr[$i] - $first;
      if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }
      if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }
}

if ( $L != -$max )
{
      # 如果有相对较小的数字，优先移至最邻近者
      splice( @arr, $l_id+1, 0, $first );
} else {
      if ( $R == $max ) {
         # 如果未找到更大的数字，直接堆到最后
         push @arr, $first;
      } else {
         # 判断数组中是否还有左边大于右边的情况
         $ok = 1;
         for my $i ( 0 .. $#arr-1 ) {
            if ( $arr[$i] > $arr[$i+1] ) {
                  splice( @arr, $i+1, 0, $first );
                  $ok = 0;
                  last;
            }
         }
         last if $ok;
      }
}
#printf "%d -- [%d]: %d, [%d]: %d\n", $first, $l_id, $L, $r_id, $R;
print join(",", @arr), "\n";
}
[/code][code]3,4,7,1,10,9,8,11,24
4,7,1,3,10,9,8,11,24
7,1,3,4,10,9,8,11,24
1,3,4,7,10,9,8,11,24
3,4,7,10,1,9,8,11,24
4,7,10,1,3,9,8,11,24
7,10,1,3,4,9,8,11,24
10,1,3,4,7,9,8,11,24
1,3,4,7,9,10,8,11,24
3,4,7,9,10,1,8,11,24
4,7,9,10,1,3,8,11,24
7,9,10,1,3,4,8,11,24
9,10,1,3,4,7,8,11,24
10,1,3,4,7,8,9,11,24
1,3,4,7,8,9,10,11,24[/code][code]2,3,5,1,4
3,5,1,2,4
5,1,2,3,4
1,2,3,4,5[/code]

老刘1号 发表于 2019-1-22 13:57

[i=s] 本帖最后由老刘1号于 2019-1-22 14:28 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217034&ptid=51910]7#[/url] [i]523066680[/i] [/b]

好思路，若完成效率应该比我那个高
250技术不忍破坏

523066680 发表于 2019-1-22 15:37

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217035&ptid=51910]8#[/url] [i]老刘1号[/i] [/b]

已更新

老刘1号 发表于 2019-1-22 16:54

[i=s] 本帖最后由老刘1号于 2019-1-22 16:55 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217036&ptid=51910]9#[/url] [i]523066680[/i] [/b]

若不考虑效率的话，感觉可以把只移动首个元素这个限制用一个算法去除掉，直接完成任意两元素交换。
[quote]a b c d e f
b <-- --> e
b c d e f a
c d e b f a
d e b f a c
e b f a c d
b f a e c d
f a e c d b
a e c d b f

a b c d e f
a <-- --> c
b c a d e f
c a d e f b
a d e f c b
d e f c b a
e f c b a d
f c b a d e
c b a d e f

a b c
a <-- --> c
b c a
c a b
a c b
c b a[/quote]
脑补算法中

523066680 发表于 2019-1-22 17:09

[i=s] 本帖最后由 523066680 于 2019-1-22 17:32 编辑 [/i]

试试粗暴一点，递归求不同解、最优解。（逻辑不够完整，怕卡太久，限制了层数 lv <= 5），[code]my @arr = qw/8 9 1 2 5/;
my @order = ();
our @ways;
solver(0, \@order, @arr);

my $first;
for my $w ( @ways )
{
printf "Solution: %s\n", join(",", @$w);
my @brr = @arr;
for my $mov ( @$w )
{
      $first = shift @brr;
      splice( @brr, $mov, 0, $first );
      printf "%s\n", join(",", @brr);
}
printf "\n";
}

sub solver
{
my ($lv, $order) = (shift, shift);
my @arr = @_;
my @brr;
my $first;
my $res;
return if $lv == 5;
if (check(\@arr) == -1) {
      #printf "[%d] %s %s\n", $lv, join(",", @arr), join(",", @brr);
      for my $i ( 1 .. $#arr ) {
         @brr = @arr[1..$#arr];
         splice(@brr, $i, 0, $arr[0] );
         $order[$lv] = $i;
         $res = solver( $lv+1, $order, @brr );
         #if ( $res == 1 ) {last;}
      }
      return 1 if $res == 1;
} else {
      #printf "%s\n", join(",", @arr);
      push @ways, [@{$order}[0..$lv-1] ];
      return 1;
}
}

sub check
{
my $ar = shift;
grep { return -1 if ( $ar->[$_] > $ar->[$_+1] ) } ( 0 .. $#$ar-1);
return 1;
}[/code][code]Solution: 1,1,4,4
9,8,1,2,5
8,9,1,2,5
9,1,2,5,8
1,2,5,8,9

Solution: 1,4,3
9,8,1,2,5
8,1,2,5,9
1,2,5,8,9

Solution: 2,4,1,3
9,1,8,2,5
1,8,2,5,9
8,1,2,5,9
1,2,5,8,9

Solution: 4,1,1,4
9,1,2,5,8
1,9,2,5,8
9,1,2,5,8
1,2,5,8,9

Solution: 4,4
9,1,2,5,8
1,2,5,8,9

[Finished in 0.1s][/code]粗暴中发现那个数组的处理过程可以更短，6次解决：[code]Move Steps: 5,5,5,2,6,5
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[/code]

523066680 发表于 2019-1-22 17:43

[i=s] 本帖最后由 523066680 于 2019-1-22 17:51 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217027&ptid=51910]1#[/url] [i]老刘1号[/i] [/b]

Tiger就是那个初中一年级，做MIT英文原版数学试卷、精通C++、Python、JAVA，熟练 PyTorch、 Tensorflow、会写CNN DNN RNN KNN，的神奇少年吗。
看到那个群里这么多大神，吓得我退群点了个外卖。

老刘1号 发表于 2019-1-22 17:51

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217039&ptid=51910]12#[/url] [i]523066680[/i] [/b]

哈哈哈，人是那个人，群不是那个群

老刘1号 发表于 2019-1-22 18:44

[i=s] 本帖最后由老刘1号于 2019-1-22 19:11 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217039&ptid=51910]12#[/url] [i]523066680[/i] [/b]

伪元素交换的算法摸清了……
找个位置真费脑……杀了一大片脑细胞[code]@echo off
Setlocal enabledelayedexpansion
::CODER BY 老刘 POWERD BY iBAT
::Set /p List=
Call :GetList 1 2 3 4 5
Call :Xchg 1 4
Call :Echo
Call :Xchg 2 3
Call :Echo
Call :Xchg 2 5
Call :Echo
Call :Xchg 3 4
Call :Echo
Pause
Exit

: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[/code][quote]4-2-3-1-5-
4-3-2-1-5-
4-5-2-1-3-
4-5-1-2-3-
请按任意键继续. . .[/quote]

523066680 发表于 2019-1-22 18:51

[i=s] 本帖最后由 523066680 于 2019-1-22 19:01 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217041&ptid=51910]14#[/url] [i]老刘1号[/i] [/b]

你用批处理，在解决问题的时候还要为批处理伤脑筋，很不容易～
要是换成其他脚本，各种骚操作、语法糖用了再说，舒服。

但仔细想想确实很蛋疼的感觉，不想写

老刘1号 发表于 2019-1-22 18:56

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217042&ptid=51910]15#[/url] [i]523066680[/i] [/b]

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

523066680 发表于 2019-1-22 19:04

[i=s] 本帖最后由 523066680 于 2019-1-22 21:36 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217043&ptid=51910]16#[/url] [i]老刘1号[/i] [/b]

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

犯了一个数组坐标偏移计算错误，花了很多时间去矫正（就是临时数组消减后下标减小了，失算）[code]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);
}
[/code]前面两个数是位置变化[code]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[/code]

老刘1号 发表于 2019-1-22 19:05

[i=s] 本帖最后由老刘1号于 2019-1-22 19:23 编辑 [/i]

补一个冒泡排序[code]@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[/code][quote]7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：80
请按任意键继续. . .
[/quote]

老刘1号 发表于 2019-1-22 19:32

[i=s] 本帖最后由老刘1号于 2019-1-22 23:51 编辑 [/i]

选择排序[code]@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[/code][quote]7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：20
请按任意键继续. . .[/quote]

search_Sudoku 发表于 2019-1-22 21:47

[size=5]1 3 5 2 [color=#00bfff]4[/color]
3 5 2 [color=#00bfff][u]1[/u] 4[/color]
5 2 [color=#00bfff]1 [u]3[/u] 4[/color]
2 [color=#00bfff]1 3 4 [u]5[/u][/color]
[color=#00bfff]1 [u]2[/u] 3 4 5[/color][/size]

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

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

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

523066680 发表于 2019-1-22 21:54

[i=s] 本帖最后由 523066680 于 2019-1-22 22:25 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217048&ptid=51910]20#[/url] [i]search_Sudoku[/i] [/b]

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

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

search_Sudoku 发表于 2019-1-22 22:12

[i=s] 本帖最后由 search_Sudoku 于 2019-1-23 10:09 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217049&ptid=51910]21#[/url] [i]523066680[/i] [/b]

子表的起始长度可以不从 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 发表于 2019-1-22 22:31

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217049&ptid=51910]21#[/url] [i]523066680[/i] [/b]

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

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

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

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

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

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

...

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

老刘1号 发表于 2019-1-23 00:09

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217044&ptid=51910]17#[/url] [i]523066680[/i] [/b]

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

523066680 发表于 2019-1-23 08:53

[i=s] 本帖最后由 523066680 于 2019-1-23 12:47 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217052&ptid=51910]24#[/url] [i]老刘1号[/i] [/b]

我先用递归跑出来一些结果，然后去强行找规律、强行解释一波，发现没什么大的漏洞就拿来用了[img]http://www.bathome.net/images/smilies/default/lol.gif[/img]。

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

[b]012[color=Red]3[/color]456[color=Red]7[/color]8  -  将7和3位置调换，可以预见的是3和7调换后，012在7的前面（成为7的前缀）；456同理；[/b][b]
[color=Silver]012[/color]3456[color=Blue]012[/color]78  - [/b][b][b]将排头的012依次插入7的前方。[/b]
[color=White]000[/color][color=Silver]3[/color]4560127[color=Blue]3[/color]8 - [/b][b][b]0127已经达成，现在开头的是数字3，将它放在数字7后面[/b]
[color=Silver][b][color=White]000[/color][/b][/color][b][color=Silver][color=White]0[/color][/color][color=Silver]456[/color]0127[/b][/b][b][b][color=Blue][b][b]456[/b][/b][/color]38 - [/b][/b][b][b]然后将前缀456插入数字3的前面。[/b]
[/b]

有了这个规则，就可以来一波语法糖[code]
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;
[/code][code][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[/code].
[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217064&ptid=51910]26#[/url] [i]search_Sudoku[/i] [/b]

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

search_Sudoku 发表于 2019-1-23 10:11

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217049&ptid=51910]21#[/url] [i]523066680[/i] [/b]

[url]http://www.bathome.net/redirect.php?goto=findpost&ptid=51910&pid=217050[/url]

[url=http://www.bathome.net/redirect.php?goto=findpost&ptid=51910&pid=217050]22楼[/url], 我做了一个不太严谨的证明

老刘1号 发表于 2019-1-23 11:19

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217050&ptid=51910]22#[/url] [i]search_Sudoku[/i] [/b]

看懂了，谢大佬

老刘1号 发表于 2019-1-23 12:00

[i=s] 本帖最后由老刘1号于 2019-1-23 12:09 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217056&ptid=51910]25#[/url] [i]523066680[/i] [/b]

简单明了、高效，学习了。
[size=4]我的思路（调换3与7）
[font=黑体]12[color=Red]3[/color]456[color=Red]7[/color]8 - 不想太多，操作3与7就等到能操作的时候再操作，其他按顺序塞到后面
[color=Silver]12[/color]345678[color=Blue]12[/color] - 此时所用步数记作step1
  [color=Silver]3[/color]4567[color=Blue]3[/color]812 - 3与7互换，∴先将3放到7后面
[color=Silver]456[/color]73812[color=Red]#[/color][color=Blue]456[/color] - 继续无脑挪到7可操作，步数记为step2
   [color=Silver]7[/color]3812[color=Blue]7[/color]456 - 将7放到原先3的位置（4之前）
   [color=Silver]38[/color]127456[color=Blue]38[/color] - 恢复原顺序，步数记为step3
[/font][/size]
由于一波操作下来除了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 发表于 2019-1-23 15:12

[i=s] 本帖最后由 523066680 于 2019-1-23 16:33 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217050&ptid=51910]22#[/url] [i]search_Sudoku[/i] [/b]

   按这个方式实现了（二分搜索没做进去），很利落[code]=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;
}
[/code][code]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[/code][code]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[/code]

老刘1号 发表于 2019-1-23 19:03

[i=s] 本帖最后由老刘1号于 2019-1-23 19:26 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217050&ptid=51910]22#[/url] [i]search_Sudoku[/i] [/b]

用批实现一个，带二分的之后补上，
[color=Red]在表尾构建有序数列（非二分检索，倒序检索）.BAT[/color][code]@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[/code][quote]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
请按任意键继续. . .[/quote][quote]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
请按任意键继续. . .[/quote]
[quote]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
请按任意键继续. . .[/quote]

页: [1]

批处理之家's Archiver

一个有限制的排序算法题