希尔排序吗?"/>
冒泡算法?太普通了,不了解一下希尔排序吗?
啥也不说了上代码
public class ShellSort {
/**
* 打印数组内容
*/
public static void saymsg(int[] src) {
int i=1;
for (int value : src) {
System.out.print("["+i+"]:"+value);
System.out.print(" ");
i++;
}
System.out.println();
}
/*** 希尔排序*/
public static void shellSort(int[] src) {double d1 = src.length;int index = 1;while (true) {d1 = Math.ceil(d1 / 2);int d = (int) d1;for (int x = 0; x < d; x++) {//比较的 【次数】 为分组的元素的个数,16个元素分两组,比较的次数为8次/*比较分组的第x+1个元素(i = x+d 每一次for循环从第二个分组开始,*每一次循环比较的是分组对应元素如第一次循环只比较分组的第一个元素,*第二次循环只比较分组的第二个元素...)* */int i = x + d;/** 假如有16个元素* 1.第一次分成两个组(d = 16/2 = 8),将两个组对应位置元素(src[0]和src[8],src[1]和src[9]...)进行比较,* 如果第二组元素小于第一组元素(src[1]>src[9]),则两个元素交换位置(详情见while循环里面的逻辑)* 2.第二次分成四组(d = 8/2 = 4),第二组和第一组元素比较(1步操作一样),然后第三组分别和第一和第二组比较,* 最后第四组和前面3组进行比较(详情见while循环里面的逻辑)* 3.以此类推,直到分的组的元素个数为一为止(d = xxx/2 = 1)* */while (i < src.length) {int j = i - d;int temp = src[i];for (; j >= 0 && temp < src[j]; j -= d) {//此处插入排序有点不同,插入排序一位一位的比较(j = j-1),这里是一组一组的比较(j = j-一组的个数)src[j + d] = src[j];}src[j + d] = temp;i = i + d;//分组加 1,如果分组的数量大于 2就拿第 n个分组和前面 n-1个分组进行比较}System.out.println("第" + (index++) + "次排序:");saymsg(src);//打印数组的,没什么用}if (d == 1)break;}System.out.println("排序完成!完成后的数组为:");saymsg(src);
}public static void main(String[] args) {int[] src ={49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99};System.out.println("原始数组排序:");saymsg(src);System.out.println("----------------------------------------------------------------------------------------------");shellSort(src);
}
}
分成两组
[1]:49 [2]:38 [3]:65 [4]:97 [5]:76 [6]:13 [7]:27 [8]:49
[9]:78 [10]:34 [11]:12 [12]:64 [13]:5 [14]:4 [15]:62 [16]:99
循环8次,每一次都是 第二组[第n次循环]和 第一组[第n次循环]进行比较(第一次循环:src[0] 和 src[0+8])
第1次循环:78>49
第2次循环:34<38,第二组元素比第一组元素的值小,所以两个元素交换位置
第3次循环:12<65,第二组元素比第一组元素的值小,所以两个元素交换位置
第4次循环:64<97,第二组元素比第一组元素的值小,所以两个元素交换位置
.......懒得写的个位应该懂[1]:49 [2]:34 [3]:12 [4]:64 [5]:5 [6]:4 [7]:27 [8]:49 [9]:78 [10]:38 [11]:65 [12]:97 [13]:76 [14]:13 [15]:62 [16]:99
分成4组
[1]:49 [2]:34 [3]:12 [4]:64
[5]:5 [6]:4 [7]:27 [8]:49
[9]:78 [10]:38 [11]:65 [12]:97
[13]:76 [14]:13 [15]:62 [16]:99
循环4次,
第1次循环:2组vs1组 5<49,第2组元素比第1组元素的值小,所以两个元素交换位置3组vs2组 78>49 2组vs1组 49>54组vs3组 76<78,第4组元素比第3组元素的值小,所以两个元素交换位置3组vs2组 76>492组vs1组 49>5[1]:5 [2]:34 [3]:12 [4]:64
[5]:49 [6]:4 [7]:27 [8]:49
[9]:76 [10]:38 [11]:65 [12]:97
[13]:78 [14]:13 [15]:62 [16]:99 第2次循环:2组vs1组 4<34,第2组元素比第1组元素的值小,所以两个元素交换位置3组vs2组 38>342组vs1组 34>44组vs3组 13<38,第4组元素比第3组元素的值小,所以两个元素交换位置3组vs2组 13<34,第3组元素比第2组元素的值小,所以两个元素交换位置2组vs1组 13>4[1]:5 [2]:4 [3]:12 [4]:64
[5]:49 [6]:13 [7]:27 [8]:49
[9]:76 [10]:34 [11]:65 [12]:97
[13]:78 [14]:38 [15]:62 [16]:99 第3次循环:12<65,第二组元素比第一组元素的值小,所以两个元素交换位置...........
第4次循环:64<97,第二组元素比第一组元素的值小,所以两个元素交换位置...........
[1]:5 [2]:4 [3]:12 [4]:64
[5]:49 [6]:13 [7]:27 [8]:49
[9]:76 [10]:34 [11]:65 [12]:97
[13]:78 [14]:38 [15]:62 [16]:99
分成8组,分成16组…以此类推直到分成的组的元素个数为1
更多推荐
冒泡算法?太普通了,不了解一下希尔排序吗?
发布评论