Java数据结构排序算法.doc

/* * To change this template, choose Tools | Templates * and open the template in the editor. */package common;/* * Description 数据结构内部排序算法集合 * author 逍遥随风翼 */public class Sorting /* * 直接插入排序(第二类),更加简洁 * param init 初始数组 * param flag 大小标记;0:由小到大 * return 有序的init数组 */ public int insertSort(int init, boolean flag) for (int i = 1; i init.length; i+) int t = initi; if (flag) if (t = 0 & initj t; j-) initj + 1 = initj; initj + 1 = t; else if (t initi - 1) int j = i - 1; for (; j = 0 & initj t; j-) initj + 1 = initj; initj + 1 = t; return init; /* * 折半插入排序 * param init 初始数组 * param flag 大小模式,true:由小到大 * return 有序的init */ public int halfInsertSort(int init, boolean flag) / 低位、高位、中位 int low; int high; int m; boolean style;/ 第一个元素不予比较 for (int i = 1; i init.length; i+) low = 0; high = i - 1; while (low = high) m = (low + high) / 2; if (flag) style = initi initm; if (initi = initm) high = m; break; else if (style) high = m - 1; else low = m + 1; int t = inithigh + 1; inithigh + 1 = initi; for (int j = i; j - 1 = high + 1; j-) if (j - 1 != high + 1) initj = initj - 1; else initj = t; return init; /* * 希尔排序 * param init 初始数值 * param increment 增量(初始为init的大小) * param flag 大小模式,true:由小到大 * return 有序的init */ public int shellSort(int init, int increment, boolean flag) /*增量采用除2计算*/ increment /= 2; for (int i = increment; i init.length; i += increment) int t = initi; if (flag) if (t = 0 & initj t; j -= increment) initj + increment = initj; initj + increment = t; else if (t initi - increment) int j = i - increment; for (; j = 0 & initj t; j -= increment) initj + increment = initj; initj + increment = t; /*只要增量大于2(考虑到非整数的情况),则递归*/ if (2 = 1) for (int i = 0; i initi + 1; else style = initi high) axis = low; int ax = initaxis;/枢轴/ flag所导致的排序方式(由大到小为true,由小到大为false) boolean style_h; boolean style_l;/ 将原始数组高低位和枢轴在数组中的位置进行记录,/ 在排序中这些数据会发生改变 int LOW = low; int HIGH = high; int AXIS = axis - low;/枢轴的位置是和当前排序序列相对应的，而不是一个固定的值. while (low axis) if (flag) style_h = inithigh ax; if (style_h) initaxis = inithigh; axis = high; else high-; while (low ax; else style_l = initlow ax; if (style_l) initaxis = initlow; axis = low; else low+; if (low = high) initlow = ax; if (LOW low - 1) QuickSort(init, LOW, low - 1, LOW + AXIS, flag); if (low + 1 HIGH) QuickSort(init, low + 1, HIGH, low + 1 + AXIS, flag); return init; /* * 简单选择排序 * param init 初始数组 * param flag 大小模式,true:由小到大 * return 有序的init */ public int SimpleSelect(int init, boolean flag) int tempo;/中间变量 boolean style;/中间判断 for (int i = 0; i init.length - 1; i+) /最后一个记录不用进行比较 for (int j = i + 1; j init.length; j+) /需要和比本身大地所有标签进行比较 if (flag) style = initj initi; if (style) tempo = initi; initi = initj; initj = tempo; return init; /* * 堆排序 * param init 初始数组 * param flag 排序模式,true:由小到大 * return 有序的init */ public int heapSort(int init, boolean flag) int tempo; /*i代表当前结点的数组坐标,j代表i的左孩子结点*/ int j; /*最初,建立大顶堆*/ for (int i = init.length / 2 - 1; i = 0; i-) tempo = initi; /*j在每次循环是必须重新赋值*/ j = 2 * i + 1; while (j = init.length - 1) /*如果i的右孩子结点比左孩子大,则用右孩子结点进行比较*/ if (j initj : initj + 1 tempo : initj = 0; i-) tempo = initi + 1; initi + 1 = init0; init0 = tempo; /*复制上面的操作*/ tempo = init0; j = 1; while (j = i) if (j initj : initj + 1 tempo : initj tempo) init(j - 1) / 2 = initj; j = 2 * j + 1; else break; init(j - 1) / 2 = tempo; return init; /* * 归并排序 * param init 初始数组 * param re 待返回的数组(初始化为与init大小相等的空数组,可直接使用init) * param s 归并的开端(初始化为init的下标) * param t 归并的末端(初始化为init的上标) * param flag 大小模式,true:由小到大 * return re 有序的init */ public int mergSort(int init, int re, int s, int t, boolean flag) /*如果归并数组大小为1,返回*/ if (s = t) res = inits; else /*归并*/ int m = (s + t) / 2; int tem = new intinit.length; mergSort(init, tem, s, m, flag);/递归 mergSort(init, tem, m + 1, t, flag); /*合并*/ int i = 0; int j = 0; int k = 0; boolean bl; for (i = s, j = m + 1, k = s; i = m & j = t; k+) if (flag) bl = temi temj; if (bl) rek = temi; i+; else rek = temj; j+; /*k在最后已经自增*/ if (i = m) for (; k = t & i = m; k+, i+) rek = temi; else for (; k = t & j = 0 & exp = exponent) int e; int k = 0; for (int i = flag ? 0 : 9; flag ? i = 0; i = flag ? +i : -i) for (int j = 0; j = exponent) radixSort(re, init, exponent, exp, flag);/递归 else /*第一次进行