文件名称：多种排序方法实现的排序器
文件大小：15KB
文件格式：JAR
更新时间：2014-04-23 06:38:25
java排序器
//插入排序 List insertSort(List list){ for(int i = 2;i <= list.getLength(); i ++){ list.getList()[0] = list.getList()[i];//复制为哨兵 int j; for(j = i-1;other.lower(list.getList()[0],list.getList()[j]);j -- ){ list.getList()[j + 1] = list.getList()[j]; }//记录后移 list.getList()[j + 1] = list.getList()[0];//插入到正确位置 } return list; } //折半插入排序 List BInsertSort(List list){ for(int i = 2; i <= list.getLength(); i ++){ list.getList()[0] = list.getList()[i];//暂存，不是哨兵作用了 int low = 1,high = i -1; while(low <= high){//折半查找要插入的位置 int m = (low + high) / 2; if(other.lower(list.getList()[0],list.getList()[m])) high = m - 1; else low = m + 1; } for(int j = i -1; j >= high + 1; j --){ list.getList()[j +1] = list.getList()[j];//记录后移 } list.getList()[high + 1] = list.getList()[0]; } return list; } //希尔排序 List shellSort(List list,int t){ int[] temp = new int[t];//增量数组 for(int i = t - 1,j = 1; i >= 0 ; i --,j += 2){ temp [i] = j; }//构造增量数组，确保最后一个元素值为1 for(int k = 0; k < t; k ++){ shellInsert(list,temp[k]);//增量为temp[k] } return list; } //一趟的希尔排序 void shellInsert(List list,int k){ //对顺序表作一趟希尔插入排序 for(int i = k + 1; i <= list.getLength(); i ++){ list.getList()[0] = list.getList()[i];//暂存，不作哨兵 int j; for(j = i - k; j > 0 && other.lower(list.getList()[0],list.getList()[j]); j -= k){ list.getList()[j + k] = list.getList()[j];//记录后移 } list.getList()[j + k] = list.getList()[0]; } //return list; } //冒泡排序 List bubbleSort(List list){ boolean change = true;//一个交换标志，当为false时，表示已排序好 int temp; for(int i = list.getLength();i >= 2 && change; i --){ change = false; for(int j = 1; j < i; j ++ ){ if(other.lower(list.getList()[j + 1], list.getList()[j])){//两个元素逆序,交换 temp = list.getList()[j + 1]; list.getList()[j + 1] = list.getList()[j]; list.getList()[j] = temp; change = true; } } } return list; } //快速排序 List quickSort(List list){ return QSort(list,1,list.getLength()); } //交换list子表的记录，使枢轴记录到位，并返回此位，在此位之前的记录均小于它，之后的记录均大于它 int partition(List list,int low,int high){ list.getList()[0] = list.getList()[low];//用子表第一个元素作枢轴,0元素为暂存枢轴 int pivotKey = list.getList()[low]; while(low < high){ while(low < high && list.getList()[high] >= pivotKey) -- high; list.getList()[low] = list.getList()[high]; while(low < high && list.getList()[low] <= pivotKey) ++ low; list.getList()[high] = list.getList()[low]; } list.getList()[low] = list.getList()[0]; return low; } //递归形式 List QSort(List list,int low,int high){ int pivotKey; if(low < high){ pivotKey = partition(list,low,high); QSort(list,low,pivotKey - 1);//递归 QSort(list,pivotKey + 1, high); } return list; } //简单选择排序 List selectSort(List list){ int j; int temp; for(int i = 1;i < list.getLength(); i ++){// j = selectMinKey(list,i);//初始化后再使用 if( i != j){ temp = list.getList()[j]; list.getList()[j] = list.getList()[i]; list.getList()[i] = temp; } } return list; } //选择最小的 int selectMinKey(List list, int k){ int min = k;// for(int i = k ; i <= list.getLength();i ++){ if(other.lower(list.getList()[i],list.getList()[min])) min = i; } return min; }