Board logo

标题: 一个有限制的排序算法题 [打印本页]
作者: 老刘1号    时间: 2019-1-22 12:17     标题: 一个有限制的排序算法题

昨天群里看到的，
【吐槽】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

我的解法(伪插入排序，效率底下，各位大佬见笑)：
  1. @echo off

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. Set /p List=

  5. Call :GetList !List!

  6. Set /A Count=1

  7. :Loop 首项逆向比较

  8. 	Set /A Flag1=0

  9. 	For /l %%a in (!prt! -1 1) Do (

  10. 		If !.1! Gtr !.%%a! (

  11. 			Call :MoveTo %%a

  12. 			Set /A Flag1=1

  13. 			Goto :JmpOut

  14. 		)

  15. 	)

  16. 	:JmpOut

  17. 	If !Flag1! Equ 1 Goto Loop

  18. 	Set /A Count+=1

  19. 	If !Count! Leq !prt! (

  20. 		Call :MoveTo !Count!

  21. 		Goto :Loop

  22. 	)

  23. 	For /l %%a in (1 1 !prt!) Do Set .%%a

  24. pause&"%~0"

  25. 

  26. :GetList

  27. 	Set /A Prt=0

  28. 	Set list=%*

  29. 	For %%a In (%*) Do (

  30. 		Set /A Prt+=1

  31. 		Set .!Prt!=%%a

  32. 	)

  33. Goto :Eof

  34. 

  35. :MoveTo 移动到原先第%1项的后面

  36. 	Set /A #=.1

  37. 	For /l %%a in (1 1 %1) Do (

  38. 		Set /A PlusOne=%%a+1

  39. 		Set /A .%%a=.!PlusOne!

  40. 	)

  41. 	Set /A .%1=#

  42. Goto :Eof
复制代码
作者: 523066680    时间: 2019-1-22 12:34

本帖最后由 523066680 于 2019-1-22 12:44 编辑

回复 1# 老刘1号

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

本帖最后由 老刘1号 于 2019-1-24 13:06 编辑

回复 2# 523066680


    刚去拷问了一波问主，原话
每次移动完以后，只能移动第一个，插入以后，列表开头就是新的可移动元素
作者: 523066680    时间: 2019-1-22 12:57

本帖最后由 523066680 于 2019-1-22 13:13 编辑

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

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

回复 5# 老刘1号
    不纠结数据结构，纠结的是描述。觉得你现在的描述就比较合理了，其他数字被动移动。
作者: 老刘1号    时间: 2019-1-22 13:10

回复 4# 523066680


    总觉得不需要纠结结构……
我觉得问主的意思就是，第一个随意移动，其余的被动移动，顺便改变位置
作者: 老刘1号    时间: 2019-1-22 13:29

补一个优化版
  1. @echo off

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. Set /p List=

  5. Call :GetList !List!

  6. Set /A Count=1

  7. :Loop

  8. 	Rem 首项逆向比较

  9. 	Set /A Flag1=0

  10. 	For /l %%a in (!prt! -1 1) Do (

  11. 		If !.1! Gtr !.%%a! (

  12. 			Call :MoveTo %%a

  13. 			set/p=移动到%%a后：<nul

  14. 			For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  15. 			Echo.

  16. 			Set /A Flag1=1

  17. 			Goto :JmpOut

  18. 		)

  19. 	)

  20. 	:JmpOut

  21. 	If !Flag1! Equ 1 Goto Loop

  22. 	

  23. 	Rem 判断是否排序完成。

  24. 	Set /A Flag2=0

  25. 	For /l %%a in (1 1 !prt!) Do (

  26. 		Set /A PlusOne=%%a+1

  27. 		Set /A "#=.!PlusOne!"

  28. 		If !#! Lss !.%%a! (

  29. 			Set Flag2=1

  30. 			If %%a equ !prt! Set Flag2=0

  31. 			Goto :JmpOut2

  32. 		)

  33. 	)

  34. 	:JmpOut2

  35. 	If !Flag2! Equ 0 Goto End

  36. 	

  37. 	Rem 继续排序

  38. 	Set /A Count+=1

  39. 	If !Count! Leq !prt! (

  40. 		Call :MoveTo !Count!

  41. 		Set/p=移动到!Count!后：<nul

  42. 		For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  43. 		Echo.

  44. 		Goto :Loop

  45. 	)

  46. 	:End

  47. 	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  48. Echo.&pause&"%~0"

  49. 

  50. :GetList

  51. 	Set /A Prt=0

  52. 	Set list=%*

  53. 	For %%a In (%*) Do (

  54. 		Set /A Prt+=1

  55. 		Set .!Prt!=%%a

  56. 	)

  57. Goto :Eof

  58. 

  59. :MoveTo 移动到原先第%1项的后面

  60. 	Set /A #=.1

  61. 	For /l %%a in (1 1 %1) Do (

  62. 		Set /A PlusOne=%%a+1

  63. 		Set /A .%%a=.!PlusOne!

  64. 	)

  65. 	Set /A .%1=#

  66. Goto :Eof
复制代码
  1. 5 1 3 2 4

  2. 移动到5后：1-3-2-4-5-

  3. 移动到2后：3-1-2-4-5-

  4. 移动到3后：1-2-3-4-5-

  5. 1-2-3-4-5-

  6. 请按任意键继续. . .

  7. 3 2 1

  8. 移动到3后：2-1-3-

  9. 移动到2后：1-2-3-

  10. 1-2-3-

  11. 请按任意键继续. . .

  12. 7 3 4 1 10 9 8 11 24

  13. 移动到4后：3-4-1-7-10-9-8-11-24-

  14. 移动到3后：4-1-3-7-10-9-8-11-24-

  15. 移动到3后：1-3-4-7-10-9-8-11-24-

  16. 移动到2后：3-1-4-7-10-9-8-11-24-

  17. 移动到2后：1-3-4-7-10-9-8-11-24-

  18. 移动到3后：3-4-1-7-10-9-8-11-24-

  19. 移动到3后：4-1-3-7-10-9-8-11-24-

  20. 移动到3后：1-3-4-7-10-9-8-11-24-

  21. 移动到4后：3-4-7-1-10-9-8-11-24-

  22. 移动到4后：4-7-1-3-10-9-8-11-24-

  23. 移动到4后：7-1-3-4-10-9-8-11-24-

  24. 移动到4后：1-3-4-7-10-9-8-11-24-

  25. 移动到5后：3-4-7-10-1-9-8-11-24-

  26. 移动到5后：4-7-10-1-3-9-8-11-24-

  27. 移动到5后：7-10-1-3-4-9-8-11-24-

  28. 移动到5后：10-1-3-4-7-9-8-11-24-

  29. 移动到7后：1-3-4-7-9-8-10-11-24-

  30. 移动到6后：3-4-7-9-8-1-10-11-24-

  31. 移动到6后：4-7-9-8-1-3-10-11-24-

  32. 移动到6后：7-9-8-1-3-4-10-11-24-

  33. 移动到6后：9-8-1-3-4-7-10-11-24-

  34. 移动到6后：8-1-3-4-7-9-10-11-24-

  35. 移动到5后：1-3-4-7-8-9-10-11-24-

  36. 1-3-4-7-8-9-10-11-24-

  37. 请按任意键继续. . .

  38. 1 2 3 5 4

  39. 移动到2后：2-1-3-5-4-

  40. 移动到2后：1-2-3-5-4-

  41. 移动到3后：2-3-1-5-4-

  42. 移动到3后：3-1-2-5-4-

  43. 移动到3后：1-2-3-5-4-

  44. 移动到4后：2-3-5-1-4-

  45. 移动到4后：3-5-1-2-4-

  46. 移动到4后：5-1-2-3-4-

  47. 移动到5后：1-2-3-4-5-

  48. 1-2-3-4-5-

  49. 请按任意键继续. . .
复制代码
作者: 523066680    时间: 2019-1-22 13:49

本帖最后由 523066680 于 2019-1-22 15:13 编辑

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

  2. my ($first, $L,$R,$r_id, $l_id, $dt);

  3. my $max = 100000;

  4. 

  5. for (1..5)

  6. {

  7.     $first = shift @arr;

  8.     $L = -$max;

  9.     $R = $max;

  10.     $r_id = 0;

  11.     $l_id = 0;

  12.     for $i ( 0 .. $#arr ) {

  13.         $dt = $arr[$i] - $first;

  14.         if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }

  15.         if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }

  16.     }

  17. 

  18.     if ( $R == $max ) {

  19.         push @arr, $first;

  20.     } else {

  21.         splice( @arr, $r_id, 0, $first );

  22.     }

  23.     #printf "%d - %d: %d, %d: %d\n", $first, $l_id, $L, $r_id, $R;

  24.     print join(",", @arr), "\n";

  25. }

  26. 

  27. #print join("", @arr);
复制代码
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

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

  2. my ($first, $L,$R,$r_id, $l_id, $dt);

  3. my $max = 100000;

  4. my $ok = 0;

  5. 

  6. while (1)

  7. {

  8.     $first = shift @arr;

  9.     $L = -$max;

  10.     $R = $max;

  11.     $r_id = 0;

  12.     $l_id = 0;

  13.     for $i ( 0 .. $#arr ) {

  14.         $dt = $arr[$i] - $first;

  15.         if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }

  16.         if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }

  17.     }

  18. 

  19.     if ( $L != -$max )

  20.     {

  21.         # 如果有相对较小的数字，优先移至最邻近者

  22.         splice( @arr, $l_id+1, 0, $first );

  23.     } else {

  24.         if ( $R == $max ) {

  25.             # 如果未找到更大的数字，直接堆到最后

  26.             push @arr, $first;

  27.         } else {

  28.             # 判断数组中是否还有 左边大于右边的情况

  29.             $ok = 1;

  30.             for my $i ( 0 .. $#arr-1 ) {

  31.                 if ( $arr[$i] > $arr[$i+1] ) {

  32.                     splice( @arr, $i+1, 0, $first );

  33.                     $ok = 0;

  34.                     last;

  35.                 }

  36.             }

  37.             last if $ok;

  38.         }

  39.     }

  40.     #printf "%d -- [%d]: %d, [%d]: %d\n", $first, $l_id, $L, $r_id, $R;

  41.     print join(",", @arr), "\n";

  42. }
复制代码
  1. 3,4,7,1,10,9,8,11,24

  2. 4,7,1,3,10,9,8,11,24

  3. 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

  6. 4,7,10,1,3,9,8,11,24

  7. 7,10,1,3,4,9,8,11,24

  8. 10,1,3,4,7,9,8,11,24

  9. 1,3,4,7,9,10,8,11,24

  10. 3,4,7,9,10,1,8,11,24

  11. 4,7,9,10,1,3,8,11,24

  12. 7,9,10,1,3,4,8,11,24

  13. 9,10,1,3,4,7,8,11,24

  14. 10,1,3,4,7,8,9,11,24

  15. 1,3,4,7,8,9,10,11,24
复制代码
  1. 2,3,5,1,4

  2. 3,5,1,2,4

  3. 5,1,2,3,4

  4. 1,2,3,4,5
复制代码
作者: 老刘1号    时间: 2019-1-22 13:57

本帖最后由 老刘1号 于 2019-1-22 14:28 编辑

回复 7# 523066680


    好思路，若完成效率应该比我那个高
250技术不忍破坏
作者: 523066680    时间: 2019-1-22 15:37

回复 8# 老刘1号

    已更新
作者: 老刘1号    时间: 2019-1-22 16:54

本帖最后由 老刘1号 于 2019-1-22 16:55 编辑

回复 9# 523066680


    若不考虑效率的话，感觉可以把只移动首个元素这个限制用一个算法去除掉，直接完成任意两元素交换。
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

脑补算法中
作者: 523066680    时间: 2019-1-22 17:09

本帖最后由 523066680 于 2019-1-22 17:32 编辑

试试粗暴一点，递归求不同解、最优解。（逻辑不够完整，怕卡太久，限制了层数 lv <= 5），
  1. my @arr = qw/8 9 1 2 5/;

  2. my @order = ();

  3. our @ways;

  4. solver(0, \@order, @arr);

  5. 

  6. my $first;

  7. for my $w ( @ways )

  8. {

  9.     printf "Solution: %s\n", join(",", @$w);

  10.     my @brr = @arr;

  11.     for my $mov ( @$w )

  12.     {

  13.         $first = shift @brr;

  14.         splice( @brr, $mov, 0, $first );

  15.         printf "%s\n", join(",", @brr);

  16.     }

  17.     printf "\n";

  18. }

  19. 

  20. sub solver

  21. {

  22.     my ($lv, $order) = (shift, shift);

  23.     my @arr = @_;

  24.     my @brr;

  25.     my $first;

  26.     my $res;

  27.     return if $lv == 5;

  28.     if (check(\@arr) == -1) {

  29.         #printf "[%d] %s %s\n", $lv, join(",", @arr), join(",", @brr);

  30.         for my $i ( 1 .. $#arr ) {

  31.             @brr = @arr[1..$#arr];

  32.             splice(@brr, $i, 0, $arr[0] );

  33.             $order[$lv] = $i;

  34.             $res = solver( $lv+1, $order, @brr );

  35.             #if ( $res == 1 ) {last;}

  36.         }

  37.         return 1 if $res == 1;

  38.     } else {

  39.         #printf "%s\n", join(",", @arr);

  40.         push @ways, [@{$order}[0..$lv-1] ];

  41.         return 1;

  42.     }

  43. }

  44. 

  45. sub check

  46. {

  47.     my $ar = shift;

  48.     grep { return -1 if ( $ar->[$_] > $ar->[$_+1] ) } ( 0 .. $#$ar-1);

  49.     return 1;

  50. }
复制代码
  1. Solution: 1,1,4,4

  2. 9,8,1,2,5

  3. 8,9,1,2,5

  4. 9,1,2,5,8

  5. 1,2,5,8,9

  6. 

  7. Solution: 1,4,3

  8. 9,8,1,2,5

  9. 8,1,2,5,9

  10. 1,2,5,8,9

  11. 

  12. Solution: 2,4,1,3

  13. 9,1,8,2,5

  14. 1,8,2,5,9

  15. 8,1,2,5,9

  16. 1,2,5,8,9

  17. 

  18. Solution: 4,1,1,4

  19. 9,1,2,5,8

  20. 1,9,2,5,8

  21. 9,1,2,5,8

  22. 1,2,5,8,9

  23. 

  24. Solution: 4,4

  25. 9,1,2,5,8

  26. 1,2,5,8,9

  27. 

  28. [Finished in 0.1s]
复制代码
粗暴中发现那个数组的处理过程可以更短，6次解决：
  1. Move Steps: 5,5,5,2,6,5

  2. 3,4,7,1,10,9,8,11,24 <- Original

  3. 4,7,1,10,9,3,8,11,24

  4. 7,1,10,9,3,4,8,11,24

  5. 1,10,9,3,4,7,8,11,24

  6. 10,9,1,3,4,7,8,11,24

  7. 9,1,3,4,7,8,10,11,24

  8. 1,3,4,7,8,9,10,11,24
复制代码
作者: 523066680    时间: 2019-1-22 17:43

本帖最后由 523066680 于 2019-1-22 17:51 编辑

回复 1# 老刘1号

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

回复 12# 523066680


    哈哈哈，人是那个人，群不是那个群
作者: 老刘1号    时间: 2019-1-22 18:44

本帖最后由 老刘1号 于 2019-1-22 19:11 编辑

回复 12# 523066680


    伪元素交换的算法摸清了……
找个位置真费脑……杀了一大片脑细胞
  1. @echo off

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. ::Set /p List=

  5. Call :GetList 1 2 3 4 5

  6. Call :Xchg 1 4

  7. Call :Echo

  8. Call :Xchg 2 3

  9. Call :Echo

  10. Call :Xchg 2 5

  11. Call :Echo

  12. Call :Xchg 3 4

  13. Call :Echo

  14. Pause

  15. Exit

  16. 

  17. :GetList

  18. 	Set /A Prt=0

  19. 	Set list=%*

  20. 	For %%a In (%*) Do (

  21. 		Set /A Prt+=1

  22. 		Set .!Prt!=%%a

  23. 	)

  24. Goto :Eof

  25. 

  26. :XChg 两元素互换

  27. 	Rem 将需要互换的第一个元素换到第一位

  28. 	Set /A SubOne=%1-1

  29. 	For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!

  30. 	Set /a Steps+=SubOne

  31. 	Rem 将需要互换的第一个元素塞到第二个元素后面

  32. 		Rem 计算新list中第二个元素的位置

  33. 		Set /A Arg2Index=%2-SubOne

  34. 		Rem 挪

  35. 		Call :MoveTo !Arg2Index!

  36. 		Set /a Steps+=1

  37. 	Rem 将需要互换的第二个元素换到第一位

  38. 	Set /a Arg2SubArg1SubOne=%2-%1-1

  39. 	For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!

  40. 	Set /a Steps+=Arg2SubArg1SubOne

  41. 	Rem 将第二个元素塞到原先第一个元素的位置

  42. 		Rem 计算新list中第一个元素之前元素的位置

  43. 		Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1

  44. 		Rem 挪

  45. 		Call :MoveTo !第一个元素之前元素的位置!

  46. 		Set /a Steps+=1

  47. 	Rem 还原其余各元素位置

  48. 	Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1

  49. 	For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!

  50. 	Set /a Steps+=Reserve

  51. Goto :Eof

  52. 

  53. :MoveTo 移动到原先第%1个元素的后面

  54. 	Set /A #=.1

  55. 	For /l %%a in (1 1 %1) Do (

  56. 		Set /A PlusOne=%%a+1

  57. 		Set /A .%%a=.!PlusOne!

  58. 	)

  59. 	Set /A .%1=#

  60. Goto :Eof

  61. 

  62. :Echo

  63. 	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  64. 	Echo.

  65. Goto :Eof
复制代码
4-2-3-1-5-
4-3-2-1-5-
4-5-2-1-3-
4-5-1-2-3-
请按任意键继续. . .
作者: 523066680    时间: 2019-1-22 18:51

本帖最后由 523066680 于 2019-1-22 19:01 编辑

回复 14# 老刘1号

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

但仔细想想确实很蛋疼的感觉，不想写
作者: 老刘1号    时间: 2019-1-22 18:56

回复 15# 523066680


    哈哈，这和批处理倒是关系不大， 主要是用“只移动第一个元素”来模拟“交换任意两个元素”比较蛋疼
作者: 523066680    时间: 2019-1-22 19:04

本帖最后由 523066680 于 2019-1-22 21:36 编辑

回复 16# 老刘1号

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

犯了一个数组坐标偏移计算错误，花了很多时间去矫正（就是临时数组消减后下标减小了，失算）
  1. my @idx = qw/0 1 2 3 4/;

  2. my ($a, $b) = (3,4);

  3. my $apos = $a;

  4. my $bpos = $b;

  5. my $exchange = 0;

  6. printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);

  7. 

  8. # 首位数插入idx[$b]的前方

  9. $first = shift @idx;

  10. splice( @idx, $b-1, 0, $first );

  11. $apos-=1;

  12. printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);

  13. 

  14. while (1)

  15. {

  16.     $first = shift @idx;

  17.     if ( $first == $a ) {

  18.         splice( @idx, $bpos, 0, $first );

  19.         $apos = $bpos;

  20.         $bpos -= 1;

  21.         $exchange = 1;

  22.     } else {

  23.         if ( $bpos ne $a ) {

  24.             if ($exchange) {

  25.                 splice( @idx, $apos-1, 0, $first );

  26.                 $bpos -= 1;

  27.             } else {

  28.                 splice( @idx, $bpos-1, 0, $first );

  29.                 $apos -= 1;

  30.             }

  31.         } else {

  32.             last;

  33.         }

  34.     }

  35.     printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);

  36. }
复制代码
前面两个数是位置变化
  1. 3 4, 0,1,2,3,4

  2. 2 4, 1,2,3,0,4

  3. 1 4, 2,3,0,1,4

  4. 0 4, 3,0,1,2,4

  5. 4 3, 0,1,2,4,3
复制代码
作者: 老刘1号    时间: 2019-1-22 19:05

本帖最后由 老刘1号 于 2019-1-22 19:23 编辑

补一个冒泡排序
  1. @echo off

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. Set /p List=

  5. Set /A Steps=0

  6. Call :冒泡排序算法 !List!

  7. Call :Echo

  8. Echo 第一个元素被移动的次数：!Steps!

  9. Pause

  10. 

  11. :冒泡排序算法

  12. 	Call :GetList %*

  13. 	:Loop

  14. 		Set Flag=0

  15. 		For /l %%a in (2 1 !prt!) Do (

  16. 			Set /A SubOne=%%a-1

  17. 			Set /A #=.!SubOne!

  18. 			If !#! Gtr !.%%a! (

  19. 				Call :XChg !SubOne! %%a

  20. 				Set /A Flag=1

  21. 			)

  22. 		)

  23. 	If !Flag! Equ 1 Goto :Loop

  24. Goto :Eof

  25. 

  26. :GetList

  27. 	Set /A Prt=0

  28. 	Set list=%*

  29. 	For %%a In (%*) Do (

  30. 		Set /A Prt+=1

  31. 		Set .!Prt!=%%a

  32. 	)

  33. Goto :Eof

  34. 

  35. :XChg 两元素互换

  36. 	Rem 将需要互换的第一个元素换到第一位

  37. 	Set /A SubOne=%1-1

  38. 	For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!

  39. 	Set /a Steps+=SubOne

  40. 	Rem 将需要互换的第一个元素塞到第二个元素后面

  41. 		Rem 计算新list中第二个元素的位置

  42. 		Set /A Arg2Index=%2-SubOne

  43. 		Rem 挪

  44. 		Call :MoveTo !Arg2Index!

  45. 		Set /a Steps+=1

  46. 	Rem 将需要互换的第二个元素换到第一位

  47. 	Set /a Arg2SubArg1SubOne=%2-%1-1

  48. 	For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!

  49. 	Set /a Steps+=Arg2SubArg1SubOne

  50. 	Rem 将第二个元素塞到原先第一个元素的位置

  51. 		Rem 计算新list中第一个元素之前元素的位置

  52. 		Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1

  53. 		Rem 挪

  54. 		Call :MoveTo !第一个元素之前元素的位置!

  55. 		Set /a Steps+=1

  56. 	Rem 还原其余各元素位置

  57. 	Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1

  58. 	For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!

  59. 	Set /a Steps+=Reserve

  60. Goto :Eof

  61. 

  62. :MoveTo 移动到原先第%1个元素的后面

  63. 	Set /A #=.1

  64. 	For /l %%a in (1 1 %1) Do (

  65. 		Set /A PlusOne=%%a+1

  66. 		Set /A .%%a=.!PlusOne!

  67. 	)

  68. 	Set /A .%1=#

  69. Goto :Eof

  70. 

  71. :Echo

  72. 	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  73. 	Echo.

  74. Goto :Eof
复制代码
7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：80
请按任意键继续. . .
作者: 老刘1号    时间: 2019-1-22 19:32

本帖最后由 老刘1号 于 2019-1-22 23:51 编辑

选择排序
  1. @echo off

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. Set /p List=

  5. Set /A Steps=0

  6. Call :选择排序算法 !List!

  7. Call :Echo

  8. Echo 第一个元素被移动的次数：!Steps!

  9. Pause

  10. 

  11. :选择排序算法

  12. 	Call :GetList %*

  13. 	Set /A Count=0

  14. 	:Loop

  15. 		Set /A Count+=1

  16. 		Set /A #=.!Count!

  17. 		For /l %%a in (!Count! 1 !prt!) Do (

  18. 			If !.%%a! Leq !#! (

  19. 				Set /A #=.%%a

  20. 				Set /A Index=%%a

  21. 			)

  22. 		)

  23. 	If !Count! Neq !Index! Call :XChg !Count! !Index!

  24. 	If !Count! Lss !prt! Goto :Loop

  25. Goto :Eof

  26. 

  27. :GetList

  28. 	Set /A Prt=0

  29. 	Set list=%*

  30. 	For %%a In (%*) Do (

  31. 		Set /A Prt+=1

  32. 		Set .!Prt!=%%a

  33. 	)

  34. Goto :Eof

  35. 

  36. :XChg 两元素互换

  37. 	Rem 将需要互换的第一个元素换到第一位

  38. 	Set /A SubOne=%1-1

  39. 	For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!

  40. 	Set /a Steps+=SubOne

  41. 	Rem 将需要互换的第一个元素塞到第二个元素后面

  42. 		Rem 计算新list中第二个元素的位置

  43. 		Set /A Arg2Index=%2-SubOne

  44. 		Rem 挪

  45. 		Call :MoveTo !Arg2Index!

  46. 		Set /a Steps+=1

  47. 	Rem 将需要互换的第二个元素换到第一位

  48. 	Set /a Arg2SubArg1SubOne=%2-%1-1

  49. 	For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!

  50. 	Set /a Steps+=Arg2SubArg1SubOne

  51. 	Rem 将第二个元素塞到原先第一个元素的位置

  52. 		Rem 计算新list中第一个元素之前元素的位置

  53. 		Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1

  54. 		Rem 挪

  55. 		Call :MoveTo !第一个元素之前元素的位置!

  56. 		Set /a Steps+=1

  57. 	Rem 还原其余各元素位置

  58. 	Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1

  59. 	For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!

  60. 	Set /a Steps+=Reserve

  61. Goto :Eof

  62. 

  63. :MoveTo 移动到原先第%1个元素的后面

  64. 	Set /A #=.1

  65. 	For /l %%a in (1 1 %1) Do (

  66. 		Set /A PlusOne=%%a+1

  67. 		Set /A .%%a=.!PlusOne!

  68. 	)

  69. 	Set /A .%1=#

  70. Goto :Eof

  71. 

  72. :Echo

  73. 	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  74. 	Echo.

  75. Goto :Eof
复制代码
7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数：20
请按任意键继续. . .
作者: search_Sudoku    时间: 2019-1-22 21:47

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    时间: 2019-1-22 21:54

本帖最后由 523066680 于 2019-1-22 22:25 编辑

回复 20# search_Sudoku

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

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

本帖最后由 search_Sudoku 于 2019-1-23 10:09 编辑

回复 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    时间: 2019-1-22 22:31

回复 21# 523066680

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

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

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

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

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

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

...

逆推到第一次插入之前, 必然在全表后部存在一个完全有序表, 这个完全有序子表最大长度为 L (也就是全表本来就是完全有序的), 最小长度是 1(表尾后部的两个元素是逆序的)
作者: 老刘1号    时间: 2019-1-23 00:09

回复 17# 523066680


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

本帖最后由 523066680 于 2019-1-23 12:47 编辑

回复 24# 老刘1号

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

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

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


有了这个规则，就可以来一波语法糖
  1. my @index = qw/0 1 2 3 4 5 6 7 8/;

  2. my ($a, $b) = (3,7);

  3. my ($apos, $bpos) = ($a, $b);

  4. my $show = sub {printf "[%d,%d] %s\n", $apos, $bpos, join(",", @index)};

  5. 

  6. $show->();

  7. # $a 的前缀转移到 $b 前面

  8. grep { splice( @index, $bpos-1, 0, shift @index ); $apos--; $show->() } (1..$a);

  9. 

  10. # $a 移到 $b 后面

  11. splice( @index, $bpos, 0, shift @index );

  12. $apos = $bpos, $bpos--;

  13. $show->();

  14. 

  15. # $b 的前缀转移到 $a 前面

  16. grep { splice( @index, $apos-1, 0, shift @index ); $bpos--; $show->() } ($a+1..$b-1);

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

  2. [2,7] 1,2,3,4,5,6,0,7,8

  3. [1,7] 2,3,4,5,6,0,1,7,8

  4. [0,7] 3,4,5,6,0,1,2,7,8

  5. [7,6] 4,5,6,0,1,2,7,3,8

  6. [7,5] 5,6,0,1,2,7,4,3,8

  7. [7,4] 6,0,1,2,7,4,5,3,8

  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    时间: 2019-1-23 10:11

回复 21# 523066680

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

22楼, 我做了一个不太严谨的证明
作者: 老刘1号    时间: 2019-1-23 11:19

回复 22# search_Sudoku


    看懂了，谢大佬
作者: 老刘1号    时间: 2019-1-23 12:00

本帖最后由 老刘1号 于 2019-1-23 12:09 编辑

回复 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    时间: 2019-1-23 15:12

本帖最后由 523066680 于 2019-1-23 16:33 编辑

回复 22# search_Sudoku

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

  2.     Ref:

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

  4. =cut

  5. 

  6. my @arr = qw/25 23 4 9 8 2 1 12 15/;

  7. my $offset;

  8. my $first;

  9. printf "%s <- Original\n", join(",", @arr);

  10. 

  11. # 查找末尾有序数组的起点

  12. $offset = $#arr+1 - seqsizes( \@arr );

  13. 

  14. while ( $offset > 0 || $arr[0] > $arr[1] )

  15. {

  16.     $first = shift @arr;

  17.     insert( \@arr, $offset, $first );

  18.     $offset--;

  19.     printf "%s\n", join(",", @arr);

  20. }

  21. 

  22. sub insert

  23. {

  24.     my ($arr, $begin, $ele) = @_;

  25.     for my $i ( $begin .. $#$arr ) {

  26.         if ($arr->[$i] > $ele ) { splice( @$arr, $i, 0, $ele ); return; }

  27.     }

  28.     splice( @$arr, $#$arr+1, 0, $ele );

  29. }

  30. 

  31. sub seqsizes

  32. {

  33.     my ($r, $size) = (shift, 1);

  34.     for my $i (1..$#$r) {

  35.         $r->[-$i] > $r->[-$i-1] ? $size++ : last;

  36.     }

  37.     return $size;

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

  2. 4,7,1,10,9,3,8,11,24

  3. 7,1,10,9,3,4,8,11,24

  4. 1,10,9,3,4,7,8,11,24

  5. 10,9,1,3,4,7,8,11,24

  6. 9,1,3,4,7,8,10,11,24

  7. 1,3,4,7,8,9,10,11,24
复制代码
  1. 25,23,4,9,8,2,1,12,15 <- Original

  2. 23,4,9,8,2,1,12,15,25

  3. 4,9,8,2,1,12,15,23,25

  4. 9,8,2,1,4,12,15,23,25

  5. 8,2,1,4,9,12,15,23,25

  6. 2,1,4,8,9,12,15,23,25

  7. 1,2,4,8,9,12,15,23,25
复制代码
作者: 老刘1号    时间: 2019-1-23 19:03

本帖最后由 老刘1号 于 2019-1-23 19:26 编辑

回复 22# search_Sudoku


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

  2. Setlocal enabledelayedexpansion

  3. ::CODER BY 老刘 POWERD BY iBAT

  4. Set /p List=

  5. Call :GetList !List!

  6. Set /A 判断次数=0,挪移次数=0

  7. 

  8. Rem 确定末尾有序数组的起始位置

  9. Set /A point=prt-1

  10. For /l %%a in (!prt! -1 2) Do (

  11. 	Set /A SubOne=%%a-1

  12. 	Set /A #=.!SubOne!

  13. 	Set /A 判断次数+=1

  14. 	If !#! Gtr !.%%a! (

  15. 		Set /A Point=SubOne

  16. 		Goto :JmpOut1

  17. 	)

  18. )

  19. :JmpOut1

  20. 

  21. Rem 挪

  22. For /l %%a in (!Point! -1 1) Do Call :挪 %%a

  23. Goto :Next

  24. 	:挪

  25. 	For /l %%b in (!prt! -1 %1) Do (

  26. 		Set /A 判断次数+=1

  27. 		If !.1! Gtr !.%%b! (

  28. 			Call :MoveTo %%b

  29. 			Set /a 挪移次数+=1

  30. 			Set/p=移到%%b后：<nul

  31. 			Call :Echo

  32. 			Goto :JmpOut2

  33. 		)

  34. 	)

  35. 	:JmpOut2

  36. 	Rem 处理首个元素比末尾有序数组全小的情况

  37. 	Set /A 判断次数+=1

  38. 	If !.1! Lss !.%1! (

  39. 		Call :MoveTo %1

  40. 		Set /a 挪移次数+=1

  41. 		Set/p=移到%1后：<nul

  42. 		Call :Echo

  43. 	)

  44. 	Goto :Eof

  45. :Next

  46. 

  47. Set 判断次数

  48. Set 挪移次数

  49. pause&"%~0"

  50. 

  51. :GetList

  52. 	Set /A Prt=0

  53. 	Set list=%*

  54. 	For %%a In (%*) Do (

  55. 		Set /A Prt+=1

  56. 		Set .!Prt!=%%a

  57. 	)

  58. Goto :Eof

  59. 

  60. :MoveTo 移动到原先第%1项的后面

  61. 	Set /A #=.1

  62. 	For /l %%a in (1 1 %1) Do (

  63. 		Set /A PlusOne=%%a+1

  64. 		Set /A .%%a=.!PlusOne!

  65. 	)

  66. 	Set /A .%1=#

  67. Goto :Eof

  68. 

  69. :Echo

  70. 	For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul

  71. 	Echo.

  72. 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
请按任意键继续. . .




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2