2.排序：希尔排序法

对int[] sorts = { 20, 9, 4, 7, 2, 6, 8, 1 };进行排序

 

 

package com.tao.test;

/**
 * 排序之初允许数据元素做较大的移动，而当数据元素接近目的地时， 再做较小的移动。这样做可以使排序过程更加快。
 * 
 */
public class TestShellSort {

	public static void main(String[] args) {
		int[] sorts = new int[] { 20, 9, 4, 7, 2, 6, 8, 1 };
		TestShellSort tss = new TestShellSort();
		tss.shellSort(sorts);
		sorts = new int[] { 20, 9, 4, 7, 2, 6, 8, 1 };
		System.out.println("=================");
		tss.ss(sorts);
	}

	/**
	 * 书本中的希尔排序法
	 * 
	 * @param sorts
	 */
	public void shellSort(int[] sorts) {
		int i, j, n = sorts.length, jump = n / 2;
		while (jump > 0) {
			for (i = jump; i <= n; i++) {
				j = i - jump; // 0++
				while (j > 0) {
					if (sorts[j - 1] > sorts[j - 1 + jump]) {
						int temp = sorts[j - 1];
						sorts[j - 1] = sorts[j - 1 + jump];
						sorts[j - 1 + jump] = temp;
						j = j - jump;
					} else {
						j = -1;
					}
					this.output(sorts);
				}
			}
			System.out.println("jump = " + jump);
			jump = jump / 2;
		}
	}

	/**
	 * 我写的希乐排序法
	 * 
	 * @param sorts
	 */
	public void ss(int[] sorts) {
		int n = sorts.length, jump = n / 2;
		while (jump > 0) {
			for (int i = 0; i < n - jump; i++) {
				if (sorts[i] > sorts[i + jump]) {
					int temp = sorts[i];
					sorts[i] = sorts[i + jump];
					sorts[i + jump] = temp;
				}
				this.output(sorts);
			}
			System.out.println(jump);
			jump /= 2;
		}
	}

	/**
	 * 用于输出信息
	 * 
	 * @param sorts
	 */
	public void output(int[] sorts) {
		for (int i = 0; i < sorts.length; i++) {
			System.out.print("  " + sorts[i]);
		}
		System.out.println();
	}
}