I initially thought about a solution that used sort but the comparison behaviour for equal items is different between perl versions:

    #!/usr/bin/perl -wl

    use strict;

    my @array = (2, 3, 4, 5, 1, 7, 11, 8, 9,  6, 10, "End" );
    my %skip  = (3 => 1, 6 => 1);
    my @new   = sort {exists $skip{$a} <=> exists $skip{$b}} @array;


    print "@new";

    __END__
    $ perl5.8.0 sort_end2.pl
    2 4 5 1 7 11 8 9 10 End 3 6

    $ perl5.6.0 sort_end2.pl
    2 End 4 5 1 7 11 8 9 10 3 6
[download]

Update: Changed the test data to make it clearer what the desired output was.

The difference is due to the the fact that 5.8 uses merge sort and 5.6 uses quick sort. From perlfunc in 5.8:

Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable,and could go quadratic. (A stable sort preserves the input order of elements that compare equal.

--
John.