老规矩，直接上图。
代码如下：
package com.collonn.algorithm.sort;
/**
* SHELL SORT
*/
public class ShellSort {
// 打印数组
private static void PrintArray(int[] s) {
System.out.printf("\n-----------------------------------");
System.out.printf("\n下标:");
for (int p = 0; p < s.length; p++) {
System.out.printf("%3d,", p);
}
System.out.printf("\n值值:");
for (Integer m : s) {
System.out.printf("%3d,", m);
}
System.out.printf("\n-----------------------------------");
}
/**
* 插入排序的变种
*
* @param start 开始下标
* @param step 步长
*/
private void insertSort(int start, int step, int[] s) {
// 大循环
int j = start + step;
for (; j < s.length; j += step) {
int i = j - step;
int t = s[j];
System.out.printf("\ntail_idx=%d, value=%d", j, t);
// 小循环，注意，比较排序是从后向前比较的，找一个较大的值，这样实现算法更直观，更优美。
for (; i >= start; i -= step) {
System.out.printf("\ncompare, value=%d, idx=%d", t, i);
if (t < s[i]) {
// 发现较小的数，向后移动
s[i + step] = s[i];
System.out.printf("\nmove, idx=%d to idx=%d", i, (i + step));
} else {
// 比前面的第一个数大，则，不用处理
if (i == j - step) {
System.out.printf("\ndo not need compare others");
}
// 发现大于等于的数，t放到此位置
s[i + step] = t;
System.out.printf("\nmove, set value=%d on idx=%d", t, (i + step));
break;
}
PrintArray(s);
}
System.out.printf("\nmin, idx=%d, start_idx=%d", i, start);
if (i < start) {
System.out.printf("\nmin set, value=%d, idx=%d", t, (i + step));
s[i + step] = t;
PrintArray(s);
}
}
}
// shell sort
public void shellSort(int[] s) {
// 步长
int step = s.length;
while (true) {
// 步长每次减半，遇到偶数加1变成奇数
step = step / 2;
if (step % 2 == 0) {
step++;
}
// 每组步长的起始下标
for (int start = 0; start < step; start++) {
System.out.printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=%d，起始下标=%d", step, start);
// 对开始下标为j步长为i的分组排序
this.insertSort(start, step, s);
}
// 当步长为1排过序后，数组已有序
if (step == 1) {
break;
}
}
}
public static void main(String[] args) {
int[] s = new int[] { 30, 25, 16, 7, 19, 20, 7, 5, 2, 8, 3, 1, 6, 9, 50 };
PrintArray(s);
ShellSort shellSort = new ShellSort();
shellSort.shellSort(s);
PrintArray(s);
}
}
执行步骤如下：
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 30, 25, 16, 7, 19, 20, 7, 5, 2, 8, 3, 1, 6, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=0
tail_idx=7, value=5
compare, value=5, idx=0
move, idx=0 to idx=7
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 30, 25, 16, 7, 19, 20, 7, 30, 2, 8, 3, 1, 6, 9, 50,
-----------------------------------
min, idx=-7, start_idx=0
min set, value=5, idx=0
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 25, 16, 7, 19, 20, 7, 30, 2, 8, 3, 1, 6, 9, 50,
-----------------------------------
tail_idx=14, value=50
compare, value=50, idx=7
do not need compare others
move, set value=50 on idx=14
min, idx=7, start_idx=0
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=1
tail_idx=8, value=2
compare, value=2, idx=1
move, idx=1 to idx=8
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 25, 16, 7, 19, 20, 7, 30, 25, 8, 3, 1, 6, 9, 50,
-----------------------------------
min, idx=-6, start_idx=1
min set, value=2, idx=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 16, 7, 19, 20, 7, 30, 25, 8, 3, 1, 6, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=2
tail_idx=9, value=8
compare, value=8, idx=2
move, idx=2 to idx=9
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 16, 7, 19, 20, 7, 30, 25, 16, 3, 1, 6, 9, 50,
-----------------------------------
min, idx=-5, start_idx=2
min set, value=8, idx=2
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 7, 19, 20, 7, 30, 25, 16, 3, 1, 6, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=3
tail_idx=10, value=3
compare, value=3, idx=3
move, idx=3 to idx=10
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 7, 19, 20, 7, 30, 25, 16, 7, 1, 6, 9, 50,
-----------------------------------
min, idx=-4, start_idx=3
min set, value=3, idx=3
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 3, 19, 20, 7, 30, 25, 16, 7, 1, 6, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=4
tail_idx=11, value=1
compare, value=1, idx=4
move, idx=4 to idx=11
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 3, 19, 20, 7, 30, 25, 16, 7, 19, 6, 9, 50,
-----------------------------------
min, idx=-3, start_idx=4
min set, value=1, idx=4
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 3, 1, 20, 7, 30, 25, 16, 7, 19, 6, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=5
tail_idx=12, value=6
compare, value=6, idx=5
move, idx=5 to idx=12
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 3, 1, 20, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
min, idx=-2, start_idx=5
min set, value=6, idx=5
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 3, 1, 6, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=7，起始下标=6
tail_idx=13, value=9
compare, value=9, idx=6
do not need compare others
move, set value=9 on idx=13
min, idx=6, start_idx=6
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=3，起始下标=0
tail_idx=3, value=3
compare, value=3, idx=0
move, idx=0 to idx=3
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 5, 2, 8, 5, 1, 6, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
min, idx=-3, start_idx=0
min set, value=3, idx=0
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 2, 8, 5, 1, 6, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
tail_idx=6, value=7
compare, value=7, idx=3
do not need compare others
move, set value=7 on idx=6
min, idx=3, start_idx=0
tail_idx=9, value=16
compare, value=16, idx=6
do not need compare others
move, set value=16 on idx=9
min, idx=6, start_idx=0
tail_idx=12, value=20
compare, value=20, idx=9
do not need compare others
move, set value=20 on idx=12
min, idx=9, start_idx=0
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=3，起始下标=1
tail_idx=4, value=1
compare, value=1, idx=1
move, idx=1 to idx=4
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 2, 8, 5, 2, 6, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
min, idx=-2, start_idx=1
min set, value=1, idx=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 8, 5, 2, 6, 7, 30, 25, 16, 7, 19, 20, 9, 50,
-----------------------------------
tail_idx=7, value=30
compare, value=30, idx=4
do not need compare others
move, set value=30 on idx=7
min, idx=4, start_idx=1
tail_idx=10, value=7
compare, value=7, idx=7
move, idx=7 to idx=10
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 8, 5, 2, 6, 7, 30, 25, 16, 30, 19, 20, 9, 50,
-----------------------------------
compare, value=7, idx=4
move, set value=7 on idx=7
min, idx=4, start_idx=1
tail_idx=13, value=9
compare, value=9, idx=10
move, idx=10 to idx=13
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 8, 5, 2, 6, 7, 7, 25, 16, 30, 19, 20, 30, 50,
-----------------------------------
compare, value=9, idx=7
move, set value=9 on idx=10
min, idx=7, start_idx=1
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=3，起始下标=2
tail_idx=5, value=6
compare, value=6, idx=2
move, idx=2 to idx=5
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 8, 5, 2, 8, 7, 7, 25, 16, 9, 19, 20, 30, 50,
-----------------------------------
min, idx=-1, start_idx=2
min set, value=6, idx=2
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 6, 5, 2, 8, 7, 7, 25, 16, 9, 19, 20, 30, 50,
-----------------------------------
tail_idx=8, value=25
compare, value=25, idx=5
do not need compare others
move, set value=25 on idx=8
min, idx=5, start_idx=2
tail_idx=11, value=19
compare, value=19, idx=8
move, idx=8 to idx=11
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 1, 6, 5, 2, 8, 7, 7, 25, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=19, idx=5
move, set value=19 on idx=8
min, idx=5, start_idx=2
tail_idx=14, value=50
compare, value=50, idx=11
do not need compare others
move, set value=50 on idx=14
min, idx=11, start_idx=2
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>步长=1，起始下标=0
tail_idx=1, value=1
compare, value=1, idx=0
move, idx=0 to idx=1
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 3, 3, 6, 5, 2, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
min, idx=-1, start_idx=0
min set, value=1, idx=0
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 3, 6, 5, 2, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
tail_idx=2, value=6
compare, value=6, idx=1
do not need compare others
move, set value=6 on idx=2
min, idx=1, start_idx=0
tail_idx=3, value=5
compare, value=5, idx=2
move, idx=2 to idx=3
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 3, 6, 6, 2, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=5, idx=1
move, set value=5 on idx=2
min, idx=1, start_idx=0
tail_idx=4, value=2
compare, value=2, idx=3
move, idx=3 to idx=4
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 3, 5, 6, 6, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=2, idx=2
move, idx=2 to idx=3
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 3, 5, 5, 6, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=2, idx=1
move, idx=1 to idx=2
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 3, 3, 5, 6, 8, 7, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=2, idx=0
move, set value=2 on idx=1
min, idx=0, start_idx=0
tail_idx=5, value=8
compare, value=8, idx=4
do not need compare others
move, set value=8 on idx=5
min, idx=4, start_idx=0
tail_idx=6, value=7
compare, value=7, idx=5
move, idx=5 to idx=6
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 8, 8, 7, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=7, idx=4
move, set value=7 on idx=5
min, idx=4, start_idx=0
tail_idx=7, value=7
compare, value=7, idx=6
move, idx=6 to idx=7
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 8, 8, 19, 16, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=7, idx=5
move, set value=7 on idx=6
min, idx=5, start_idx=0
tail_idx=8, value=19
compare, value=19, idx=7
do not need compare others
move, set value=19 on idx=8
min, idx=7, start_idx=0
tail_idx=9, value=16
compare, value=16, idx=8
move, idx=8 to idx=9
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 7, 8, 19, 19, 9, 25, 20, 30, 50,
-----------------------------------
compare, value=16, idx=7
move, set value=16 on idx=8
min, idx=7, start_idx=0
tail_idx=10, value=9
compare, value=9, idx=9
move, idx=9 to idx=10
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 7, 8, 16, 19, 19, 25, 20, 30, 50,
-----------------------------------
compare, value=9, idx=8
move, idx=8 to idx=9
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 7, 8, 16, 16, 19, 25, 20, 30, 50,
-----------------------------------
compare, value=9, idx=7
move, set value=9 on idx=8
min, idx=7, start_idx=0
tail_idx=11, value=25
compare, value=25, idx=10
do not need compare others
move, set value=25 on idx=11
min, idx=10, start_idx=0
tail_idx=12, value=20
compare, value=20, idx=11
move, idx=11 to idx=12
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 7, 8, 9, 16, 19, 25, 25, 30, 50,
-----------------------------------
compare, value=20, idx=10
move, set value=20 on idx=11
min, idx=10, start_idx=0
tail_idx=13, value=30
compare, value=30, idx=12
do not need compare others
move, set value=30 on idx=13
min, idx=12, start_idx=0
tail_idx=14, value=50
compare, value=50, idx=13
do not need compare others
move, set value=50 on idx=14
min, idx=13, start_idx=0
-----------------------------------
下标: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
值值: 1, 2, 3, 5, 6, 7, 7, 8, 9, 16, 19, 20, 25, 30, 50,
-----------------------------------
原文：http://blog.csdn.net/collonn/article/details/19814193