给定定义已排序子数组的数组索引，如果元素小于最大元素并在1上递归，则将元素放在子数组末尾的子数组正上方

//package com.nowjava;


public class Main {// from N o w  J a v a  .   c o m

    /** Given array indices that define a sorted subarray, place the element

     * just above the subarray at the end of the subarray if it is smaller

     * than the largest element and recurse on a 1-smaller subarray.

     * 

     * @param a  the array to work on

     * @param begin  the index of the beginning of the sorted subarray

     * @param end  the index of the end of the sorted subarray */

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

            T[] a, int begin, int end) {

        /* pre: end is not the last element of a */

        if (begin <= end) {

            if (a[end + 1].compareTo(a[end]) == -1) {

                swap(a, end, end + 1);

                insertInOrderRecursive(a, begin, end - 1);

            }

        }

    }


    /** Swap two elements of an array given their indices.

     * 

     * @param a  the array to work on

     * @param first  the index of the first element to swap

     * @param second  the index of the second element to swap

     */

    public