* 内部排序
* 1，insert
* 2，shell
* 3，
*/
public class SortInMemory {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []num={1,2,3,5,6,8,9,11,13,19,200,1,2,3,5,9};
        insert_Sort sort=new insert_Sort();
        sort.sort(num);
        System.out.println("insert排序结果：");
        sort.show(num);
        shell_sort sort2=new shell_sort();
        sort2.shell(num);
        System.out.println("shell排序结果：");
        sort2.show(num);
    }
}

class Sort{
    public void show(int a[]) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "  ");
        }
        System.out.println();
    }
}

/*
* 插入排序算法
* java实现
*/
class insert_Sort extends Sort{
    
    public void sort(int []a){
        //System.out.println(a.length);
        for (int i = 1; i < a.length; i++) {
            /*
             * 两种方式实现插入排血的内部移位及插入处理
             */
//            int tem=a[i];
//            int j=i;
//            while (j>0&&tem<a[j-1]) {//tem<a[j-1]&&j>0 如果这样的话，当j=0的时候a[j-1]是非法的，所以要先判断j>0;
//                a[j]=a[j-1];
//                j--;
//            }
//            a[j]=tem;
            int tem=a[i];
            int j=i;
            for(;j>0;j--){
                if(tem>a[j-1]){
                    a[j]=a[j-1];
                }
                else {//一定要在不用移位时及时跳出循环
                    break;
                }
            }
            a[j]=tem;
        }
    }
}

/**
* @author hai
* 内部排序里的shell排序
*/

public class shell_sort extends Sort{
    /**
     * @author hai
     *len 步长；
     *start 起始下标；
     *r 排序数组；
     */
    private void insert_sort(int start, int len, int[] r) {
        for (int i = len+start; i < r.length; i+=len) {
            int j=i;
            int tem=r[i];
            for(;j>len;j-=len){
                if(tem>r[j-len]){
                    r[j]=r[j-len];
                }else {
                    break;
                }
            }
            r[j]=tem;
        }
    }
    /**
     * @author hai
     *r 排序的数组；
     */
    public void shell(int []r) {
        int length,len;
        length=r.length;
        for (len=length/2;len>0;len/=2) {//分组
            for(int j=1;j<=len;j++){
                insert_sort(j, len, r);//每一组调用插入排序
            }
        }
    }

}