希尔排序（java实现）

「爱情、让人受尽委屈。」 2022-06-01 12:39 158阅读 0赞

#### 希尔排序基于插入排序，比选择排序和插入排序这种复杂度为0（n^2）的效率快，比快速排序和其他排序复杂度为（n\*logN）的慢,但非常容易实现，代码既短又简单，希尔排序在最坏情况和在平均情况下执行效率相差不大。 ####

希尔排序用java实现

package sort;  
  
import java.util.Random;

/\*\*  
 \* 希尔排序  
 \* @author 灰太狼  
 \*  
 \*/  
  
class ArraySh  
\{  
    private long\[\] theArray;  
    private int nElems;//数组元素个数  
      
    public ArraySh(int max) \{  
        theArray=new long\[max\];  
        nElems=0;  
    \}  
      
    //插入数据  
    public void insert(long value) \{  
        theArray\[nElems\]=value;  
        nElems++;  
    \}  
      
    public void display() \{  
        System.out.print("arr=");  
        for(int i=0;i<theArray.length;i++) \{  
            System.out.print(theArray\[i\]+" ");  
        \}  
        System.out.println();  
    \}  
      
    //排序  
    public void sort() \{  
        int inner,outer;  
        long temp;  
        int h=1;//增量间隔  
        while(h<=nElems/3) \{  
            h=h\*3+1;//生成间隔序列(1,4,13,40,121,...)  
        \}  
        //h=4  
        //间隔不断减少，直至间隔为1  
        while(h>0) \{  
            for(outer=h;outer<nElems;outer++) \{  
                  
                temp=theArray\[outer\];  
                inner=outer;  
                //以4为增量间隔，子排序区间为（0,4,8），（1,5,9）（2,6）（3,7）  
                while(inner>h-1&&theArray\[inner-h\]>=temp) \{  
                      
                    theArray\[inner\]=theArray\[inner-h\];  
                    inner-=h;  
                \}  
                theArray\[inner\]=temp;  
                  
            \}  
            h=(h-1)/3;  
        \}  
          
    \}  
      
\}  
public class ShellSort \{  
      
    public static void main(String \[\]args) \{  
        int maxSize=10;//数组大小  
        ArraySh arr=new ArraySh(maxSize);  
        Random r=new Random();  
          
        for(int j=0;j<maxSize;j++) \{  
            long n=r.nextInt(100);  
            arr.insert(n);  
        \}  
        arr.display();  
        arr.sort();  
        arr.display();  
    \}  
\}