几种常用排序算法

    最近刚上班，在公司每天除了学习业务以外就是打打酱油，利用空余时间整理了几个排序算法

/**
 * @author txin0814 E-mail:[e-mail]
 * @version 1.0
 * @date Apr 1, 2011 2:28:06 PM
 * @description 排序类的 基类
 */

public abstract class BaseSorter<E extends Comparable<E>> {
	
	public abstract void sort(E[] array,int from,int len);
	
	public final void sort(E[] array){
		sort(array,0,array.length);
	}
	
	protected final void swap(E[] array,int from,int to){
		E temp = array[from];
		array[from] = array[to];
		array[to] = temp;
	}
}

/**
 * @author txin0814 E-mail:[e-mail]
 * @version 1.0
 * @date Apr 1, 2011 2:34:47 PM
 * @description 插入排序 该算法在数据规模小的时候十分高效，
 * 				该算法每次插入第K+1到前K个有序数组中一个合适位置，
 * 				K从0开始到N-1,从而完成排序
 */

public class InsertSorter<E extends Comparable<E>> extends BaseSorter<E>{
	
	//当SORT_TYPE为false时按降序排列 为TRUE时按升序排列
	public static boolean SORT_TYPE = false; 

	@Override
	public void sort(E[] array, int from, int len) {
		E tmp=null;
        for(int i=from+1;i<from+len;i++){
            tmp=array[i];
            int j=i;
            for(;j>from;j--){
            	if(SORT_TYPE){
            		if(tmp.compareTo(array[j-1])<0){
                        array[j]=array[j-1];
                    }else break;
            	}else{
            		if(tmp.compareTo(array[j-1])>0){
                        array[j]=array[j-1];
                    }else break;
            	}
            }
            array[j]=tmp;
        }
        
        /*for (E e : array) {
			System.out.println(e);
		}*/

	}

	public static void main(String[] args) {
		Integer[] elem = {32, 43, 1, 3, 54, 4, 19};
		InsertSorter<Integer> insertsort = new InsertSorter<Integer>();
		//InsertSorter.SORT_TYPE = true;
		insertsort.sort(elem);
		for (Integer integer : elem) {
			System.out.println(integer);
		}
	}
}


/**
 * @author txin0814 E-mail:[e-mail]
 * @version 1.0
 * @date Apr 1, 2011 2:53:29 PM
 * @description 冒泡排序 算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置。
 * 				i从0一直到N-1从而完成排序。（当然也可以从数组开始端开始比较相邻两元素，
 * 				把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)
 */

public class BubbleSorter<E extends Comparable<E>> extends BaseSorter<E> {

	//当SORT_TYPE为false时按降序排列 为TRUE时按升序排列
	public static boolean SORT_TYPE = false; 

	public final void bubble_down(E[] array, int from, int len) {
		for (int i = from; i < from + len; i++) {
			for (int j = from + len - 1; j > i; j--) {
				if (array[j].compareTo(array[j - 1]) > 0) {
					swap(array, j - 1, j);
				}
			}
		}
	}

	public final void bubble_up(E[] array, int from, int len) {
		for (int i = from + len - 1; i >= from; i--) {
			for (int j = from; j < i; j++) {
				if (array[j].compareTo(array[j + 1]) > 0) {
					swap(array, j + 1, j );
				}
			}
		}
	}

	@Override
	public void sort(E[] array, int from, int len) {
		if (SORT_TYPE) {
			bubble_up(array, from, len);
		} else {
			bubble_down(array, from, len);
		}
	}
	
	public static void main(String[] args) {
		Integer[] elem = {32, 43, 1, 3, 54, 4, 19};
		BubbleSorter<Integer> bsort = new BubbleSorter<Integer>();
		//BubbleSorter.DWON = true;
		//bsort.sort(elem);
		//BubbleSorter.SORT_TYPE = true;
		bsort.sort(elem, 0, elem.length);
		for (Integer integer : elem) {
			System.out.println(integer);
		}
	}

}

/**
 * @author txin0814 E-mail:[e-mail]
 * @version 1.0
 * @date Apr 1, 2011 3:17:42 PM
 * @description 选择排序 选择排序相对于冒泡来说，它不是每次发现逆序都交换，
 * 				而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。
 * 				相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了
 */

public class SelectSorter<E extends Comparable<E>> extends BaseSorter<E> {

	@Override
	public void sort(E[] array, int from, int len) {
		for (int i = 0; i < len; i++){
			int smallest = i;
			int j = i + from;
			for(;j < from + len ; j++){
				if(array[j].compareTo(array[smallest]) < 0){
					smallest = j;
				}
			}
			swap(array,i,smallest);
		}
	}
	
	public static void main(String[] args){
		Integer[] elem = {12,20,2,5,1,25,55,15};
		SelectSorter<Integer> sort = new SelectSorter<Integer>();
		sort.sort(elem);
		for (Integer integer : elem) {
			System.out.println(integer);
		}
	}

}