package com.company;
public class ShellSort {
/**
* 希尔排序其实是插入排序的变种
* 在这里姑且先用非递归排序实现
* 此算法
* 只不过它有步长的设定
* 即,根据步长来对整个数组进行分组
* 不过每个分组中的元素都是间距相同
* 的两个元素
* 然后对每组进行排序
* 其实也是分而治之算法的体现
* @param sourceArray
*/
static public void shellSort0(int[] sourceArray) {
int arrayLength = sourceArray.length;
//一开始的步长。
int stepWidth = arrayLength;
//因为最后的步长肯定会变成1的
//这也就意味着最后一次排序的进行了
while (stepWidth > 1) {
//姑且把步长设置为原来步长的1/2吧
stepWidth /= 2;
//打印
System.out.println("步长为" + stepWidth);
//我之所以这样写是因为我觉得
//1、步长会越来越小
//2、所有步长相邻的元素都可以从开始
//被遍历到。
//但是这样写会使整个实现变得很长
for (int counter = 0;counter < stepWidth;counter++) {
//现在开始进行一小趟的排序
//通过插入排序法对每个元素进行排序
//需要被插入的index
int stepIndex = 1;
//这个元素的index不能超出数组范围
while (counter + stepIndex * stepWidth < arrayLength) {
int insertIndex = counter + stepIndex * stepWidth;
//先保存这个待插入的元素值
int tempElement = sourceArray[insertIndex];
//元素该插入的位置。
int targetIndex = counter;
for (int counter0 = counter;counter0 < counter + stepIndex * stepWidth;counter0+=stepWidth) {
if (tempElement > sourceArray[counter0]) {
targetIndex = counter0;
//移动元素
for (int counter1 = insertIndex;counter1 > targetIndex;counter1-=stepWidth)
sourceArray[counter1] = sourceArray[counter1 - stepWidth];
//插入元素
sourceArray[targetIndex] = tempElement;
break;
} else continue;
}
//打印每一分组的元素状况。
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("第" + stepIndex + "次交换结束了");
stepIndex++;
}
//打印每一趟的元素状况。
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("第" + (counter + 1) + "趟结束了\n");
}
}
}
/**
* 上面的方法写得过于冗长
* 本方法是参照了网上的版本
* 把代码写得精简了一些
* @param sourceArray
*/
static public void shellSort1(int[] sourceArray) {
int arrayLength = sourceArray.length;
//上面那个while循环完全可以写成for循环
for (int stepWidth = arrayLength / 2;stepWidth >= 1;stepWidth /= 2){
//因为上面的方法比较长,所以此处需要改写。
//毕竟插入排序算法是从第2个元素开始的
//其实就相当于步长为1了
//而现在是步长是大于了
//那么就是说可以从1*stepWidth开始
//下面这样写是把插入和遍历整个数组的思想结合起来了
//这种写法的宏观着眼点是针对每个元素采取不同的方式来处理
//我上面的着眼点是一个个单独的相邻步长的元素
//我上面的写法总是直接切入没拐弯
for (int counter = stepWidth;counter < arrayLength;counter++) {
//这个还是保存需要被插入的元素值
int tempElement = sourceArray[counter];
//这样就把下标变成从0开始了
int counter0 = counter - stepWidth;
//它是从后往前遍历,只要不满足这个条件就代表找到位置了
//而我是从前往后正向遍历——很麻烦!
//从后往前写给人的感觉思路非常清晰
//并且这样遍历到每个元素,它之前的元素
//都已经是排好序的了
while (counter0 >= 0 && tempElement > sourceArray[counter0]) {
sourceArray[counter0 + stepWidth] = sourceArray[counter0];
counter0 -= stepWidth;
}
sourceArray[counter0 + stepWidth] = tempElement;
}
//打印每一趟的元素状况。
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("步长 " + stepWidth + " 的趟结束了\n");
}
}
}
希尔排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入,时间为O(n*n); 冒泡排序 最优(对于升序的数组,因为加入了一个跳出判断):O(n),...
- 给定数组 int[] arr = {3,6,8,4,7,5,9,1,2,0};使用至少三种方法对数组arr排序(作...
- 实现两种初级的排序算法: 选择排序思路 首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果...