复习java基础的时候，顺手写的。代码比较丑……
1、直接插入排序

public static <T extends Comparable<T>> T[] straight_insert_sorting(T []ts){
    int len = ts.length;
    T temp;
    for(int i=1; i<len; i++)
    {
        temp = ts[i];
        int j = i-1;
        while (j>=0){
            if(temp.compareTo(ts[j]) <= 0)
            {
                ts[j+1] = ts[j];
                j--;
            }
            else {
                ts[j+1] = temp;
                break;
            }
        }
        if(j<0) ts[0] = temp;
    }
    return ts;
}

2、希尔排序

 public static <T extends Comparable<T>> T[]shell_sort(T[]ts){
    int len = ts.length;
    T temp;
    for(int gap = len/2;gap>0;gap/=2){
        for(int j=gap;j<len;j++){
            temp = ts[j];
            while (( (j-gap)>=0 ) && (temp.compareTo(ts[j-gap]) < 0)){
                ts[j] = ts[j-gap];
                j = j-gap;
            }
            ts[j] = temp;
        }
    }
    return ts;
}

3、简单选择排序

 public static <T extends Comparable<T>>T[]select_sort(T[]ts){
    int len = ts.length;
    T min,temp;
    int pos;
    for (int i=0;i<len;i++){
        pos = i;
        min = ts[i];
        for (int j=i+1;j<len;j++){
            if(ts[j].compareTo(min) < 0 )
            {
                min = ts[j];
                pos = j;
            }
        }
        if(pos>i) {
            temp = ts[i];
            ts[i] = ts[pos];
            ts[pos] = temp;
        }
    }
    return ts;
}

4、堆排序

  public static <T extends Comparable<T>>T[]heap_sort(final T[]ts){

    final int len = ts.length;
    class HeapBuilder{
        public  void  build_max_heap(){
            for (int i = (len-2)/2;i>=0;i--){
                max_heap(i,len);
            }
        }

        void max_heap(int root,int len){
          //  System.out.println("root is:"+ts[root]);
            int left = 2 * root + 1;
            int right = left + 1;
            int largest = left;

            if (left > len-1) return;
            if ((right < len-1) && ts[right].compareTo(ts[largest])>0 )
                largest = right;
            if(ts[root].compareTo(ts[largest]) > 0) largest = root;

            if(ts[root].compareTo(ts[largest]) < 0) {
                T temp = ts[root];
                ts[root] = ts[largest];
                ts[largest] = temp;
                max_heap(largest,len);
            }
            
        }
    }
    HeapBuilder hb = new HeapBuilder();
    hb.build_max_heap();
    for (int i=len-1;i>=1;i--){
        /*System.out.print("\nheap:");
        for (T t:ts)
            System.out.print(t.toString()+" ");*/

        T temp = ts[i];
        ts[i] = ts[0];
        ts[0] = temp;

        if(i==1) break;

        hb.max_heap(0,i);
    }

    return ts;
}