黑马程序员技术交流社区
标题:
【已重置】
[打印本页]
作者:
胡永城
时间:
2013-12-7 23:07
标题:
【已重置】
本帖最后由 胡永城 于 2017-2-21 21:32 编辑
【已重置】
作者:
吴琼cola
时间:
2013-12-8 10:00
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]--;
}
}
}
}
作者:
天下
时间:
2013-12-8 10:33
本帖最后由 天下 于 2013-12-8 10:39 编辑
献丑了:
/**希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值
* 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强
* 版的插入排序
* 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列
* 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序,
*/
public class ShellSort {
public static void shellSort(int[] arr) {
int j = 0;
int temp = 0;
for (int increment = arr.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < arr.length; i++) {
temp = arr[i];
for (j = i; j >= increment; j -= increment) {
if(temp > arr[j - increment]){
arr[j] = arr[j - increment];
}else{
break;
}
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = new int[] {5, 2, 8, 9, 1, 3,4};
int[] arr1=new int[]{ 5, 2, 8, 6, 9, 7, 1, 3, 10, 4};
System.out.println("未排序前");
print(arr);
System.out.println();
print(arr1);
shellSort(arr);
shellSort(arr1);
System.out.println("\n排序后");
print(arr);
System.out.println();
print(arr1);
}
public static void print(int[] arr){
for(int i: arr){
System.out.print(i+" ");
}
}
}
打印结果:
未排序前
5 2 8 9 1 3 4
5 2 8 6 9 7 1 3 10 4
排序后
9 8 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2