数组插入排序

/**

 * Licensed to the Apache Software Foundation (ASF) under one or more

 * contributor license agreements.  See the NOTICE file distributed with

 * this work for additional information regarding copyright ownership.

 * The ASF licenses this file to You under the Apache License, Version 2.0

 * (the "License"); you may not use this file except in compliance with

 * the License.  You may obtain a copy of the License at

 *

 *     http://www.apache.org/licenses/LICENSE-2.0

 *

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

import java.util.Collection;
/*来自 
 时 代 J a v a - N o w J a v a . c o m*/

import java.util.Comparator;


public class Main{

    public static <T> void insertionSort(T[] a, int fromIndex, int toIndex,

            Comparator<? super T> comp) {

        if (toIndex - fromIndex <= 1)

            return;

        getSorter(a, comp).insertionSort(fromIndex, toIndex - 1);

    }

    public static <T> void insertionSort(T[] a, Comparator<? super T> comp) {
    /** 
    来 自 
    N o w J a v a . c o m - 时  代  Java
    **/

        insertionSort(a, 0, a.length, comp);

    }

    public static <T extends Comparable<? super T>> void insertionSort(

            T[] a, int fromIndex, int toIndex) {

        if (toIndex - fromIndex <= 1)

            return;

        getSorter(a).insertionSort(fromIndex, toIndex - 1);

    }

    public static <T extends Comparable<? super T>> void insertionSort(T[] a) {

        insertionSort(a, 0, a.length);

    }

    private static <T> SorterTemplate getSorter(final T[] a,

            final Comparator<? super T> comp) {

        return new SorterTemplate() {

            @Override

            protected void swap(int i, int j) {

                final T o = a[i];

                a[i] = a[j];

                a[j] = o;

            }


            @Override

            protected int compare(int i, int j) {

                return comp.compare(a[i], a[j]);

            }


            @Override

            protected void setPivot(int i) {

                pivot = a[i];

            }


            @Override

            protected int comparePivot(int j) {

                return comp.compare(pivot, a[j]);

            }


            private T pivot;

        };

    }

    private static <T extends Comparable<? super T>> SorterTemplate getSorter(

            final T[] a) {

        return new SorterTemplate() {

            @Override

            protected void swap(int i, int j) {

                final T o = a[i];

                a[i] = a[j