| Blog信息 |
|
blog名称:小鸟吹烟
日志总数:157
评论数量:424
留言数量:-1
访问次数:1265299
建立时间:2006年10月23日 |
| |
|
 [J2SE]排序2
文章收藏, 网上资源
tone 发表于 2007/3/6 14:36:54 |
|
插入排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498735.aspx
冒泡排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498736.aspx
选择排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498742.aspx
归并排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498746.aspx
希尔排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498764.aspx
快速排序：http://blog.csdn.net/Linyco/archive/2005/10/10/498759.aspx |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:53:19 |
| package Utils.Sort;
/**
*快速排序，要求待排序的数组必须实现Comparable接口
*/
public class QuickSort implements SortStrategy
{
private static final int CUTOFF = 3; //当元素数大于此值时采用快速排序
/**
*利用快速排序算法对数组obj进行排序，要求待排序的数组必须实现了
comparable接口
*/
public void sort(Comparable[] obj)
{
if (obj == null)
{
throw new NullPointerException("The argument can not be null!");
}
quickSort(obj, 0, obj.length - 1);
}
/**
*对数组obj快速排序
*@param obj 待排序的数组
*@param left 数组的下界
*@param right 数组的上界
*/
private void quickSort(Comparable[] obj, int left, int right)
{
if (left + CUTOFF > right)
{
SortStrategy ss = new ChooseSort();
ss.sort(obj);
}
else
{
//找出枢轴点，并将它放在数组最后面的位置
pivot(obj, left, right);
int i = left, j = right - 1;
Comparable tmp = null;
while (true)
{
//将i, j分别移到大于/小于枢纽值的位置
/*因为数组的第一个和倒数第二个元素分别小于和大于枢纽元，所以不会发生数组越界*/
while (obj[++i].compareTo(obj[right - 1]) < 0) {}
while (obj[--j].compareTo(obj[right - 1]) > 0) {}
//交换
if (i < j)
{
tmp = obj[i];
obj[i] = obj[j];
obj[j] = tmp;
}
else
break;
}
//将枢纽值与i指向的值交换
tmp = obj[i];
obj[i] = obj[right - 1];
obj[right - 1] = tmp;
//对枢纽值左侧和右侧数组继续进行快速排序
quickSort(obj, left, i - 1);
quickSort(obj, i + 1, right);
}
}
/**
*在数组obj中选取枢纽元，选取方法为取数组第一个、中间一个、最后一个元素中中间的一个。将枢纽元置于倒数第二个位置，三个中最大的放在数组最后一个位置，最小的放在第一个位置
*@param obj 要选择枢纽元的数组
*@param left 数组的下界
*@param right 数组的上界
*/
private void pivot(Comparable[] obj, int left, int right)
{
int center = (left + right) / 2;
Comparable tmp = null;
if (obj[left].compareTo(obj[center]) > 0)
{
tmp = obj[left];
obj[left] = obj[center];
obj[center] = tmp;
}
if (obj[left].compareTo(obj[right]) > 0)
{
tmp = obj[left];
obj[left] = obj[right];
obj[right] = tmp;
}
if (obj[center].compareTo(obj[right]) > 0)
{
tmp = obj[center];
obj[center] = obj[right];
obj[center] = tmp;
}
//将枢纽元置于数组的倒数第二个
tmp = obj[center];
obj[center] = obj[right - 1];
obj[right - 1] = tmp;
}
} |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:52:17 |
| package Utils.Sort;
/**
*希尔排序，要求待排序的数组必须实现Comparable接口
*/
public class ShellSort implements SortStrategy
{
private int[] increment;
/**
*利用希尔排序算法对数组obj进行排序
*/
public void sort(Comparable[] obj)
{
if (obj == null)
{
throw new NullPointerException("The argument can not be null!");
}
//初始化步长
initGap(obj);
//步长依次变化（递减）
for (int i = increment.length - 1 ;i >= 0 ;i-- )
{
int step = increment[i];
//由步长位置开始
for (int j = step ;j < obj.length ;j++ )
{
Comparable tmp;
//如果后面的小于前面的（相隔step），则与前面的交换
for (int m = j ;m >= step ;m = m - step )
{
if (obj[m].compareTo(obj[m - step]) < 0)
{
tmp = obj[m - step];
obj[m - step] = obj[m];
obj[m] = tmp;
}
//因为之前的位置必定已经比较过，所以这里直接退出循环
else
{
break;
}
}
}
}
}
/**
*根据数组的长度确定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i)
+ 1和9 * pow(4, i) - 9 * pow(2, i) + 1
*@return int[] 两个公式的最大指数
*@param length 数组的长度
*/
private int[] initExponent(int length)
{
int[] exp = new int[2];
exp[0] = 1;
exp[1] = -1;
int[] gap = new int[2];
gap[0] = gap[1] = 0;
//确定两个公式的最大指数
while (gap[0] < length)
{
exp[0]++;
gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
}
exp[0]--;
while (gap[1] < length)
{
exp[1]++;
gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
}
exp[1]--;
return exp;
}
private void initGap(Comparable[] obj)
{
//利用公式初始化增量序列
int exp[] = initExponent(obj.length);
int[] gap = new int[2];
increment = new int[exp[0] + exp[1]];
//将增量数组由大到小赋值
for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- )
{
gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
//将大的增量先放入增量数组，这里实际上是一个归并排序
//不需要考虑gap[0] == gap[1]的情况，因为不可能出现相等。
if (gap[0] > gap[1])
{
increment[i] = gap[0];
exp[0]--;
}
else
{
increment[i] = gap[1];
exp[1]--;
}
}
}
} |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:50:20 |
| package Utils.Sort;
/**
*归并排序，要求待排序的数组必须实现Comparable接口
*/
public class MergeSort implements SortStrategy
{
private Comparable[] bridge;
/**
*利用归并排序算法对数组obj进行排序
*/
public void sort(Comparable[] obj)
{
if (obj == null)
{
throw new NullPointerException("The param can not be null!");
}
bridge = new Comparable[obj.length]; //初始化中间数组
mergeSort(obj, 0, obj.length - 1); //归并排序
bridge = null;
}
/**
*将下标从left到right的数组进行归并排序
*@param obj 要排序的数组的句柄
*@param left 要排序的数组的第一个元素下标
*@param right 要排序的数组的最后一个元素的下标
*/
private void mergeSort(Comparable[] obj, int left, int right)
{
if (left < right)
{
int center = (left + right)/2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
/**
*将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序
*@param obj 对象数组的句柄
*@param left 左数组的第一个元素的下标
*@param center 左数组的最后一个元素的下标
*@param right 右数组的最后一个元素的下标
*/
private void merge(Comparable[] obj, int left, int center, int right)
{
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right)
{
//从两个数组中取出小的放入中间数组
if (obj[left].compareTo(obj[mid]) <= 0)
{
bridge[third++] = obj[left++];
}
else
bridge[third++] = obj[mid++];
}
//剩余部分依次置入中间数组
while (mid <= right)
{
bridge[third++] = obj[mid++];
}
while (left <= center)
{
bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
/**
*将中间数组bridge中的内容拷贝到原数组中
*@param obj 原数组的句柄
*@param left 要拷贝的第一个元素的下标
*@param right 要拷贝的最后一个元素的下标
*/
private void copy(Comparable[] obj, int left, int right)
{
while (left <= right)
{
obj[left] = bridge[left];
left++;
}
}
} |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:39:44 |
| package Utils.Sort;
/**
*@author Linyco
*利用选择排序法对数组排序，数组中元素必须实现了Comparable接口。
*/
public class ChooseSort implements SortStrategy
{
/**
*对数组obj中的元素以选择排序算法进行排序
*/
public void sort(Comparable[] obj)
{
if (obj == null)
{
throw new NullPointerException("The argument can not be null!");
}
Comparable tmp = null;
int index = 0;
for (int i = 0 ;i < obj.length - 1 ;i++ )
{
index = i;
tmp = obj[i];
for (int j = i + 1 ;j < obj.length ;j++ )
{
//对邻接的元素进行比较，如果后面的小，就记下它的位置
if (tmp.compareTo(obj[j]) > 0)
{
tmp = obj[j]; //要每次比较都记录下当前小的这个值!
index = j;
}
}
//将最小的元素交换到前面
tmp = obj[i];
obj[i] = obj[index];
obj[index] = tmp;
}
}
} |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:38:15 |
| package Utils.Sort;
/**
*@author Linyco
*利用冒泡排序法对数组排序，数组中元素必须实现了Comparable接口。
*/
public class BubbleSort implements SortStrategy
{
/**
*对数组obj中的元素以冒泡排序算法进行排序
*/
public void sort(Comparable[] obj)
{
if (obj == null)
{
throw new NullPointerException("The argument can not be null!");
}
Comparable tmp;
for (int i = 0 ;i < obj.length ;i++ )
{
//切记，每次都要从第一个开始比。最后的不用再比。
for (int j = 0 ;j < obj.length - i - 1 ;j++ )
{
//对邻接的元素进行比较，如果后面的小，就交换
if (obj[j].compareTo(obj[j + 1]) > 0)
{
tmp = obj[j];
obj[j] = obj[j + 1];
obj[j + 1] = tmp;
}
}
}
}
} |
|
|
回复:排序2
文章收藏, 网上资源
tone发表评论于2007/3/6 14:37:48 |
| package Utils.Sort;
/**
*插入排序，要求待排序的数组必须实现Comparable接口
*/
public class InsertSort implements SortStrategy
{
/**
*利用插入排序算法对obj进行排序
*/
public void sort(Comparable []obj)
{
if (obj == null)
{
throw new NullPointerException("The argument can not be null!");
}
/*
*对数组中的第i个元素，认为它前面的i - 1个已经排序好，然后将它插入到前面的i - 1个元素中
*/
int size = 1;
while (size < obj.length)
{
insert(obj, size++, obj[size - 1]);
}
}
/**
*在已经排序好的数组中插入一个元素，使插入后的数组仍然有序
*@param obj 已经排序好的数组
*@param size 已经排序好的数组的大小
*@param c 待插入的元素
*/
private void insert(Comparable []obj, int size, Comparable c)
{
for (int i = 0 ;i < size ;i++ )
{
if (c.compareTo(obj[i]) < 0)
{
System.out.println(obj[i]);
//如果待插入的元素小于当前元素，则把当前元素后面的元素依次后移一位
for (int j = size ;j > i ;j-- )
{
obj[j] = obj[j - 1];
}
obj[i] = c;
break;
}
}
}
} |
|
» 1 »
|
如果你忍了，欺负你的人将来可能就进监狱了。如果你反击，欺负你的人将来可能就获选十大杰出青年了。