shellsortimp.java

用JAVA实现排序等简单算法的演示

package algorithmImp;

public class ShellSortImp extends SortAlgorithmImp {
	protected static final int MAX_SEQ_SIZE = 10;
	protected int[] shellSeq = new int[MAX_SEQ_SIZE]; 
	
	public void sorting() {
		int seqSize = initShellSeq();
		
		for (int seqIndex = 0; seqIndex < seqSize; seqIndex++) {
			int seq = shellSeq[seqIndex];
			for (int scanIndex = seq; scanIndex < data.length; scanIndex++) {
				select(scanIndex);		// 选择当前正在扫描元素，查找其合适的插入位置
				int insertPos = scanIndex - seq;
				for (; insertPos >= 0; insertPos = insertPos - seq) {
					if (compareSelectedWith(insertPos)) break;
					else moveElement(insertPos, insertPos+seq);
				}
				// 将原先保存的当前正在扫描元素放（插入）到合适位置
				if (scanIndex > insertPos+seq) placeSelectedData(insertPos+seq);
			}
		}
	}
	
	private int initShellSeq() {
		int[] internalSeq = {1, 5, 9, 17, 33, 65, 129, 257};
//		int[] internalSeq = {1, 3, 7, 15, 31, 63, 127, 255};
		
		int index;
		for (index = 0; index < internalSeq.length; index++) {
			if (data.length < internalSeq[index]*2) break;
		}
		if (index > 0) index = index - 1;
		for (int i = index; i >= 0; i--) shellSeq[index-i] = internalSeq[i];
		return index+1;
	}

}