Shell Sort希尔排序Java实现

/**	希尔排序Java实现
 * 	by puladiao
 * 	http://blog.verypod.com
 */
 
import java.util.Random;

class ShellSort {
	int[] arr;

	public ShellSort(int num) {
		arr = new int[num];
	}
	
	// 将arr数组初始化为随机数数组
	public void randomArray() {
		Random rd = new Random();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rd.nextInt(arr.length * 2);
		}
	}

	// 将arr数组初始化为倒序数组
	public void reverseArray() {
		for (int i = 0; i < arr.length; i++) {
			arr[i] = arr.length - i;
		}
	}

	// 打印数组
	public void display() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("");
	}

	// 希尔排序
	public void shellSort() {
		int increment = 1;
		while (increment < arr.length) {
			increment = increment * 3 + 1;
		}
		increment = (increment - 1) / 3;
		while (increment >= 1) {
			for (int i = 0; i < increment; i++) {
				insertSort(i, increment);
			}
			display();
			increment = (increment - 1) / 3;
		}
	}
	
	// 插入排序,该方法会被希尔排序调用,该方法也可以直接使用,使用方法为 insertSort(0,1);
	// startIndex是排序起始索引,increment为增量,即元素之间的空间
	public void insertSort(int startIndex, int increment) {
		for (int i = startIndex + increment; i < arr.length; i += increment) {
			int j = i - increment;
			// System.out.println(i);
			int temp = arr[i];
			while (j >= startIndex && temp < arr[j]) {
				arr[j + increment] = arr[j];
				j -= increment;
			}
			arr[j + increment] = temp;
		}
	}
}

public class ShellSortApp {
	public static void main(String[] args) {
		ShellSort ss = new ShellSort(100);
		ss.reverseArray();
		ss.display();
		ss.shellSort();
		ss.display();
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注