几种常用排序算法

几种常用排序算法
几种常用排序算法

几种常用排序算法
/** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 2:28:06 PM * @description 排序类的 基类 */ public abstract class BaseSorter { 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:[email protected] * @version 1.0 * @date Apr 1, 2011 2:34:47 PM * @description 插入排序 该算法在数据规模小的时候十分高效, * 该算法每次插入第K+1到前K个有序数组中一个合适位置, * K从0开始到N-1,从而完成排序 */ public class InsertSorter extends BaseSorter{ //当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;ifrom;j--){ if(SORT_TYPE){ 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 insertsort = new InsertSorter(); //InsertSorter.SORT_TYPE = true; insertsort.sort(elem); for (Integer integer : elem) { System.out.println(integer); } } } /** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 2:53:29 PM * @description 冒泡排序 算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置.) */ public class BubbleSorter extends BaseSorter { //当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 bsort = new BubbleSorter(); //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:[email protected] * @version 1.0 * @date Apr 1, 2011 3:17:42 PM * @description 选择排序 选择排序相对于冒泡来说,它不是每次发现逆序都交换, * 而是在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序.