奔走在算法的大路上（一）排序之希尔排序

我就是我 2022-08-05 14:22 51阅读 0赞

希尔排序是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序最关键的是选对增量，关于增量的选择，建议参考：http://zh.wikipedia.org/wiki/希尔排序  中的步长序列。

希尔排序的核心思想是：由一定规则将带排序的长序列切割成多个子序列，子序列进行内部插入排序，如此循环。这个规则就是增量。

package Sort;
 
 public class ShellSort {
 
 	/**
 	 * 
 	 * 是否小于
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:14:52
 	 * @param v
 	 * @param w
 	 * @return
 	 */
 	private static boolean less(Comparable v,Comparable w){
 		return v.compareTo(w)<0;
 	}
 	/**
 	 * 
 	 * 交换函数
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:14:32
 	 * @param a
 	 * @param i
 	 * @param j
 	 */
 	private static void exch(Comparable[] a,int i ,int j){
 		 Comparable t = a[i];
 		 a[i] = a[j];
 		 a[j] = t;
 	 }
 	/**
 	 * 
 	 * 打印输出
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月3日 下午4:19:03
 	 * @param a
 	 */
 	private static void show(Comparable[] a){
 		for(int i = 0; i < a.length; i++){
 			System.out.print(a[i] + " ");
 		}
 		System.out.println();
 	}
 	
 	/**
 	 * 
 	 * 希尔排序
 	 * 
 	 * @author zhangjunshuai
 	 * @date 2015年4月8日 下午8:51:28
 	 * @param a
 	 */
 	private static void Shell(Comparable[] a){
 		int N = a.length/2;
 		while(N>0){//增量的判断
 			for(int i=0;i<a.length;i++){//开始循环所有数据
 				int M = (a.length-i-1)/N;//计算i后面还有多少N
 				for(int j=1;j<=M;j++){//以插入排序的方式排序增量为N的数
 					for(int h = j;h>0;h--){
 						if(less(a[i+h*N],a[i+(h-1)*N]))
 							exch(a,i+h*N,i+(h-1)*N);
 						else
 							h=-1;
 					}
 				}
 			}
 			System.out.println("--------------增量："+N);
 			show(a);
 			N =N/2;
 		}
 	}
 	public static void main(String[] args) {
 		Integer[] a = {49,38,65,97,76,13,27,49,55,4};
 		Shell(a);
 	}
 	
 
 }

结果：

![Center][]

第一遍内部对比的组合是（颜色相同的组合）

![Center 1][]

第二遍内部对比的组合是（颜色相同的组合）

![Center 2][]

第三遍是对相邻的进行插入的排序

参考：

http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/

[Center]: /images/20220805/81e13ed1001249bc8c86bdc28dfd4d33.png
[Center 1]: /images/20220805/b630554e955d4075849fdf1d6622e668.png
[Center 2]: /images/20220805/0de35f30d2c54eda9308585baf8bc6a1.png