设l是数组l中相等间距的项的子集，包含l中n个总项中的n个。

// 来自 n o w j a v a . c o m


//package com.nowjava;

import java.util.ArrayList;


public class Main {

    /**

     * Let l be a subset of entries in an array L that are equally spaced, containing n of the N total entries in L.

     * Also assume that the first n-1 entries in l are already sorted in ascending order.

     * This function inserts the nth element of l into its proper place among the other n-1 entries so that, ignoring the

     *  rest of the entries in L, the elements that constitute l are in order.

     *  

     *  

     *  example:

     *  sortedStart = index(A)

     *  unsortedStart = index(C)

     *  spacing = 5

     *  

     *  xxAxxxxDxxxxExxxxCxxxxBxxxx    [ ]

     *  xxAxxxxDxxxxExxxx_xxxxBxxxx -> [C]

     *  xxAxxxxDxxxx_xxxxExxxxBxxxx    [C]

     *  xxAxxxx_xxxxDxxxxExxxxBxxxx    [C]

     *  xxAxxxxCxxxxDxxxxExxxxBxxxx <- [ ]

     *  

     * 

     * @param arrayList the ArrayList that you want to be partially sorted

     * @param sortedStart the index of the first element in the sorted subset of the array. All elements $spacing apart between this

     *         and $unsortedStart are sorted

     * @param unsortedStart the index of arrayList that marks the element that you want to insert into the sported section.

     *         it could already be in the right place, but we're not sure

     */

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

            ArrayList<T> arrayList, int sortedStart, int unsortedStart,

            int spacing) {

        T insertElement = arrayList.get(unsortedStart);

        int insertIndex = unsortedStart;

        while (insertIndex != sortedStart

                && insertElement.comp