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);
}COPY

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,3COPY

@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 :EofCOPY

@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 :EofCOPY

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;COPY

[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,8COPY

=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;
}COPY

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,24COPY

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,25COPY

@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 :EofCOPY