[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

一个有限制的排序算法题

昨天群里看到的,
【吐槽】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. :GetList
  26. Set /A Prt=0
  27. Set list=%*
  28. For %%a In (%*) Do (
  29. Set /A Prt+=1
  30. Set .!Prt!=%%a
  31. )
  32. Goto :Eof
  33. :MoveTo 移动到原先第%1项的后面
  34. Set /A #=.1
  35. For /l %%a in (1 1 %1) Do (
  36. Set /A PlusOne=%%a+1
  37. Set /A .%%a=.!PlusOne!
  38. )
  39. Set /A .%1=#
  40. Goto :Eof
复制代码

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

回复 1# 老刘1号

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

TOP

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

回复 2# 523066680


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

TOP

本帖最后由 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号
    不纠结数据结构,纠结的是描述。觉得你现在的描述就比较合理了,其他数字被动移动。

TOP

回复 4# 523066680


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

TOP

补一个优化版
  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. Rem 判断是否排序完成。
  23. Set /A Flag2=0
  24. For /l %%a in (1 1 !prt!) Do (
  25. Set /A PlusOne=%%a+1
  26. Set /A "#=.!PlusOne!"
  27. If !#! Lss !.%%a! (
  28. Set Flag2=1
  29. If %%a equ !prt! Set Flag2=0
  30. Goto :JmpOut2
  31. )
  32. )
  33. :JmpOut2
  34. If !Flag2! Equ 0 Goto End
  35. Rem 继续排序
  36. Set /A Count+=1
  37. If !Count! Leq !prt! (
  38. Call :MoveTo !Count!
  39. Set/p=移动到!Count!后:<nul
  40. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  41. Echo.
  42. Goto :Loop
  43. )
  44. :End
  45. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  46. Echo.&pause&"%~0"
  47. :GetList
  48. Set /A Prt=0
  49. Set list=%*
  50. For %%a In (%*) Do (
  51. Set /A Prt+=1
  52. Set .!Prt!=%%a
  53. )
  54. Goto :Eof
  55. :MoveTo 移动到原先第%1项的后面
  56. Set /A #=.1
  57. For /l %%a in (1 1 %1) Do (
  58. Set /A PlusOne=%%a+1
  59. Set /A .%%a=.!PlusOne!
  60. )
  61. Set /A .%1=#
  62. 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. 请按任意键继续. . .
复制代码

TOP

本帖最后由 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. for (1..5)
  5. {
  6.     $first = shift @arr;
  7.     $L = -$max;
  8.     $R = $max;
  9.     $r_id = 0;
  10.     $l_id = 0;
  11.     for $i ( 0 .. $#arr ) {
  12.         $dt = $arr[$i] - $first;
  13.         if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }
  14.         if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }
  15.     }
  16.     if ( $R == $max ) {
  17.         push @arr, $first;
  18.     } else {
  19.         splice( @arr, $r_id, 0, $first );
  20.     }
  21.     #printf "%d - %d: %d, %d: %d\n", $first, $l_id, $L, $r_id, $R;
  22.     print join(",", @arr), "\n";
  23. }
  24. #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. while (1)
  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.     if ( $L != -$max )
  18.     {
  19.         # 如果有相对较小的数字,优先移至最邻近者
  20.         splice( @arr, $l_id+1, 0, $first );
  21.     } else {
  22.         if ( $R == $max ) {
  23.             # 如果未找到更大的数字,直接堆到最后
  24.             push @arr, $first;
  25.         } else {
  26.             # 判断数组中是否还有 左边大于右边的情况
  27.             $ok = 1;
  28.             for my $i ( 0 .. $#arr-1 ) {
  29.                 if ( $arr[$i] > $arr[$i+1] ) {
  30.                     splice( @arr, $i+1, 0, $first );
  31.                     $ok = 0;
  32.                     last;
  33.                 }
  34.             }
  35.             last if $ok;
  36.         }
  37.     }
  38.     #printf "%d -- [%d]: %d, [%d]: %d\n", $first, $l_id, $L, $r_id, $R;
  39.     print join(",", @arr), "\n";
  40. }
复制代码
  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

评分人数

TOP

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

回复 7# 523066680


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

评分人数

    • 523066680: 是的判断未写完,不知道会不会推倒重来PB + 1

TOP

回复 8# 老刘1号

    已更新

TOP

本帖最后由 老刘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

脑补算法中

TOP

本帖最后由 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. my $first;
  6. for my $w ( @ways )
  7. {
  8.     printf "Solution: %s\n", join(",", @$w);
  9.     my @brr = @arr;
  10.     for my $mov ( @$w )
  11.     {
  12.         $first = shift @brr;
  13.         splice( @brr, $mov, 0, $first );
  14.         printf "%s\n", join(",", @brr);
  15.     }
  16.     printf "\n";
  17. }
  18. sub solver
  19. {
  20.     my ($lv, $order) = (shift, shift);
  21.     my @arr = @_;
  22.     my @brr;
  23.     my $first;
  24.     my $res;
  25.     return if $lv == 5;
  26.     if (check(\@arr) == -1) {
  27.         #printf "[%d] %s %s\n", $lv, join(",", @arr), join(",", @brr);
  28.         for my $i ( 1 .. $#arr ) {
  29.             @brr = @arr[1..$#arr];
  30.             splice(@brr, $i, 0, $arr[0] );
  31.             $order[$lv] = $i;
  32.             $res = solver( $lv+1, $order, @brr );
  33.             #if ( $res == 1 ) {last;}
  34.         }
  35.         return 1 if $res == 1;
  36.     } else {
  37.         #printf "%s\n", join(",", @arr);
  38.         push @ways, [@{$order}[0..$lv-1] ];
  39.         return 1;
  40.     }
  41. }
  42. sub check
  43. {
  44.     my $ar = shift;
  45.     grep { return -1 if ( $ar->[$_] > $ar->[$_+1] ) } ( 0 .. $#$ar-1);
  46.     return 1;
  47. }
复制代码
  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. Solution: 1,4,3
  7. 9,8,1,2,5
  8. 8,1,2,5,9
  9. 1,2,5,8,9
  10. Solution: 2,4,1,3
  11. 9,1,8,2,5
  12. 1,8,2,5,9
  13. 8,1,2,5,9
  14. 1,2,5,8,9
  15. Solution: 4,1,1,4
  16. 9,1,2,5,8
  17. 1,9,2,5,8
  18. 9,1,2,5,8
  19. 1,2,5,8,9
  20. Solution: 4,4
  21. 9,1,2,5,8
  22. 1,2,5,8,9
  23. [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
复制代码

TOP

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

回复 1# 老刘1号

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

TOP

回复 12# 523066680


    哈哈哈,人是那个人,群不是那个群

TOP

本帖最后由 老刘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. :GetList
  17. Set /A Prt=0
  18. Set list=%*
  19. For %%a In (%*) Do (
  20. Set /A Prt+=1
  21. Set .!Prt!=%%a
  22. )
  23. Goto :Eof
  24. :XChg 两元素互换
  25. Rem 将需要互换的第一个元素换到第一位
  26. Set /A SubOne=%1-1
  27. For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
  28. Set /a Steps+=SubOne
  29. Rem 将需要互换的第一个元素塞到第二个元素后面
  30. Rem 计算新list中第二个元素的位置
  31. Set /A Arg2Index=%2-SubOne
  32. Rem 挪
  33. Call :MoveTo !Arg2Index!
  34. Set /a Steps+=1
  35. Rem 将需要互换的第二个元素换到第一位
  36. Set /a Arg2SubArg1SubOne=%2-%1-1
  37. For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
  38. Set /a Steps+=Arg2SubArg1SubOne
  39. Rem 将第二个元素塞到原先第一个元素的位置
  40. Rem 计算新list中第一个元素之前元素的位置
  41. Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
  42. Rem 挪
  43. Call :MoveTo !第一个元素之前元素的位置!
  44. Set /a Steps+=1
  45. Rem 还原其余各元素位置
  46. Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
  47. For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
  48. Set /a Steps+=Reserve
  49. Goto :Eof
  50. :MoveTo 移动到原先第%1个元素的后面
  51. Set /A #=.1
  52. For /l %%a in (1 1 %1) Do (
  53. Set /A PlusOne=%%a+1
  54. Set /A .%%a=.!PlusOne!
  55. )
  56. Set /A .%1=#
  57. Goto :Eof
  58. :Echo
  59. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  60. Echo.
  61. Goto :Eof
复制代码
4-2-3-1-5-
4-3-2-1-5-
4-5-2-1-3-
4-5-1-2-3-
请按任意键继续. . .
1

评分人数

TOP

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

回复 14# 老刘1号

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

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

TOP

返回列表