基本的排序算法
插入排序
选择排序
快速排序
。。。。
后续补充
package org.jf.alg.sort;/** * * 数组排序工具类 * * 数组中不能有空元素 * * @author junfeng.chen * */public class Sorter {/** * * 选择排序 * 算法思想：将待排序的集合分为两部分，一部分为已排序的部分，一部分为未排序部分 * 开始时，未排序部分为整个集合，已排序部分为空 * 算法步骤： * 每次从待排序的集合中找出最大(或最小)的元素,将该元素与集合中第一个元素交换；此时该 * 元素及以前的元素都为排好序的 * * i<-- [0 - size-1] * j<-- [i+1 - size-1]//未排好序的元素 i-size-1 * find min from [i+1 - size - 1] * * exchange min and a[i] * * O(n2) * @param objs */public static void selectSort(Comparable [] objs){if(objs==null || objs.length<=1)return;for(int i=0;i<objs.length-1;i++){Comparable little = objs[i];int little_indx = i;for(int j=i+1;j<=objs.length-1;j++){if(objs[j].compareTo(little)<0){little = objs[j];little_indx = j;}}if(little_indx != i){Comparable tmp = objs[i];objs[i] = objs[little_indx];objs[little_indx] = tmp;}}}/** * * 将数组分成两部分，一部分为已排序不分，另一部分未排序 * 开始时，已排序不分为空集合；未排序不分为整个数组 * 每次取未排序部分的第一个元素，插入到已排序部分的适当位置 * * * 插入排序 * @param objs */public static void insertSort(Comparable objs[]){for(int i=0;i<objs.length;i++){Comparable max = objs[i];for(int j=0;j<i;j++){if(objs[j].compareTo(max)>0)//找到位置{for(int k = i;k>j;k--)//后面的元素 依次后移{objs[k] = objs[k - 1];}objs[j]=max;break;}}}}/** * *取首元素作为基准 * @param objs * @param start * @param end */public static int partition(Comparable objs[],int start,int end){Comparable pivot = objs[start];int left = start;int right = end;while(left < right){while(pivot.compareTo(objs[right])<0)right --;while(left < right &&pivot.compareTo(objs[left])>=0){left ++ ;}if(left < right){Comparable tmp = objs[left];objs[left] = objs[right];objs[right] = tmp;}}int pos = right;objs [start] = objs[pos];objs [pos] = pivot;return pos;}/** * 三数取中 作为基准 * @param objs * @param start * @param end * @return */@SuppressWarnings({ "rawtypes", "unchecked" })public static int partition2(Comparable objs[],int start,int end){int left = start;int right = end;int mid_indx = (left+right)/2;Comparable mid = objs[(left+right)/2];if(objs[left].compareTo(mid)<0){if(mid.compareTo(objs[right])<=0)mid_indx =mid_indx ;//pivot = mid;else{if( objs[left].compareTo(objs[right])>0)mid_indx = left;//pivot = objs[left];else mid_indx = right;//pivot = objs[right];}}else{if(mid.compareTo(objs[right])>=0)mid_indx = mid_indx;//pivot = mid;else{if(objs[left].compareTo(objs[right])>=0)mid_indx = right;//pivot = objs[right];elsemid_indx = left;//pivot = objs[left];}}Comparable tp = objs[start];objs[start] = objs[mid_indx];objs[mid_indx] = tp;Comparable pivot = objs[start];while(left < right){while(pivot.compareTo(objs[right])<0)right --;while(left < right &&pivot.compareTo(objs[left])>=0){left ++ ;}if(left < right){Comparable tmp = objs[left];objs[left] = objs[right];objs[right] = tmp;}}int pos = right;objs [start] = objs[pos];objs [pos] = pivot;return pos;}public static void quickSort(Comparable objs[],int start,int end){if(start >= end)return;int pos = partition2(objs,start,end);quickSort(objs,start,pos -1);quickSort(objs,pos+1,end);}/** * 快速排序 * 采用3位取中法 定基准 * @param objs */public static void quickSort(Comparable objs[]){quickSort(objs,0,objs.length-1);}}