希尔排序[Java实现]

希尔排序基本思想：先将整个待排序序列分割成若干子序列，每个子序列由相差一定长度的数据元素组成(这个相差的长度称为增量)，然后我们分别对这些子序列进行直接插入排序[个人认为是交换排序]，一轮排序后再取第二个增量，以此类推，需要注意的是，对于希尔排序中增量的确定没有统一的规定，通常做法是：第一个增量为待排序序列长度的二分之一(取整)，然后逐渐减半(取整)，直到等于1为止。

代码：

package org.pbdevj.ds.sort.insert;/**希尔排序*/public class ShellSort implements ISort {private Element[] elements;public ShellSort() {// TODO Auto-generated constructor stub}public ShellSort(Element[] elements) {// TODO Auto-generated constructor stubthis.elements = elements;}@Overridepublic void output() {// TODO Auto-generated method stubif (elements!=null){for (Element e : elements) {System.out.println(e);}}}@Overridepublic void sort() {// TODO Auto-generated method stub// TODO Auto-generated method stubif (elements==null || elements.length==0 || elements.length==1)return;Element te;for (int k = elements.length/2; k > 0; k–) {//增量循环递减//分组方向1//for (int i = 0; i+k<elements.length; i++) {//if(elements[i].compareTo(elements[i+k])>0){//如果左元素大于右元素则交换//te = elements[i];//elements[i] = elements[i+k];//elements[i+k]=te;//}//}//分组方向2for (int i = k; i<elements.length; i++) {if(elements[i-k].compareTo(elements[i])>0){//如果左元素大于右元素则交换te = elements[i-k];elements[i-k] = elements[i];elements[i]=te;}}}}@Overridepublic void sort(ISortCallBack sortCallBack) {// TODO Auto-generated method stubsort();}}

测试代码：

package org.pbdevj.ds.sort.insert.utest;import org.pbdevj.ds.sort.insert.BinaryInsertSort;import org.pbdevj.ds.sort.insert.Element;import org.pbdevj.ds.sort.insert.ISort;import org.pbdevj.ds.sort.insert.ShellSort;public class ShellSortTest {/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubElement[] elements=new Element[]{new Element(90),new Element(60),new Element(70),new Element(60),new Element(70),new Element(40),new Element(90),new Element(10)};ISort sort = new ShellSort(elements);System.out.println(“before sort….”);sort.output();System.out.println(“start sort…..”);sort.sort();System.out.println(“after sort…”);sort.output();}}

要永不言弃坚持到底百折不挠宁死不屈，但我们好多人没想过，