堆排序和shell排序

近来很热啊，菜鸟准备放水了。在写一篇夏雨的脑洞文，喜欢雨。

相关的原理与细节，看视频，我讲不清楚了，汗啊。

python03-05-05希尔排序
计算机科学9.2&9.3希尔排序与堆排序（浙江大学陈越、何钦铭

概念嘛，百度百科
堆排序
Shell排序

堆的形状如下

堆.jpg

采用大根堆，根结点从0开始，其左儿子为2i+1,右儿子为2i+2, 在[0,(n-1)/2]之间循环建立堆。

相关的code

package day20180728;

public class DuiSort {
    
    /**
     * 
    建大根堆的函数。
    
     */
    public static void heap(int[] arr,int k,int n){
        
        int i=k,j=2*i+1;
        
        while(j<n) //筛选进行到叶子的判别方法。
        {
    
            if(j<n-1&&arr[j]<arr[j+1])
            {
                j=j+1;  
            }
            
            if(arr[i]<arr[j])
            {
                int temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                i=j;
                j=2*i+1;
            }else {
                break;
            }   
        }
        
    }
    

    public static void heapSort(int[] arr,int n)
    {
        int temp,i=0;
         for(i=(n-1)/2; i>=0; i--)
         {
             heap(arr,i,n);
             display(arr);
         }
        
         for(i=1; i<n; i++)
         {
             temp=arr[0];
             arr[0]=arr[n-i];
             arr[n-i]=temp;
             heap(arr,0,n-i);  
             System.out.println("第"+i+"建堆的情况:");
             display(arr);
         }
        
    }
    
    public static void display(int[] arr)
    {
        for(int i:arr)
        {
            System.out.print(i+" ");
        }
        System.out.println();
        
    }

    public static void main(String[] args) {
        
        
        int[] arr= {11,6,8,666,-5,33,88,6};
        
        heapSort(arr,arr.length);
        

    }

}

结果如下

11 6 8 666 -5 33 88 6 
11 6 88 666 -5 33 8 6 
11 666 88 6 -5 33 8 6 
666 11 88 6 -5 33 8 6 
第1建堆的情况:
88 11 33 6 -5 6 8 666 
第2建堆的情况:
33 11 8 6 -5 6 88 666 
第3建堆的情况:
11 6 8 6 -5 33 88 666 
第4建堆的情况:
8 6 -5 6 11 33 88 666 
第5建堆的情况:
6 6 -5 8 11 33 88 666 
第6建堆的情况:
6 -5 6 8 11 33 88 666 
第7建堆的情况:
-5 6 6 8 11 33 88 666 

shell排序

就是改变增量的插入排序，这里增量采用n/2递归到0，

相关的code

package day20180728;

public class ShellSort {
    
    public static void shell(int[] arr,int k)
    {
        
        for(int i=k; i<arr.length; i=i+1)
        {
            
               int temp=0;
                temp=arr[i];
                int m=i-k;  
                 //这里的判断index是坑，先判断它，不然会下标越界。
                while(m>=0&&arr[m]>temp)
                {
                    arr[m+k]=arr[m];
                     m=m-k; 
                }
                if(m!=i)
                    arr[m+k]=temp;
            
            System.out.println("第"+i+"次结果");
            display(arr);
            
        }
        
    }

public  static void  shellSort(int[] arr)
{
    for(int k=arr.length/2; k>0; k=k/2)
        shell(arr,k);
}
    
    public static void display(int[] arr)
    {
        for(int i:arr)
        {
            System.out.print(i+" ");
        }
        System.out.println();
        
    }
    

    public static void main(String[] args) {
    
        int[] arr= {11,6,8,666,-5,33,88,6};
        display(arr);
        
        shellSort(arr);
        
        display(arr);
        

    }

}

结果

11 6 8 666 -5 33 88 6 
第4次结果
-5 6 8 666 11 33 88 6 
第5次结果
-5 6 8 666 11 33 88 6 
第6次结果
-5 6 8 666 11 33 88 6 
第7次结果
-5 6 8 6 11 33 88 666 
第2次结果
-5 6 8 6 11 33 88 666 
第3次结果
-5 6 8 6 11 33 88 666 
第4次结果
-5 6 8 6 11 33 88 666 
第5次结果
-5 6 8 6 11 33 88 666 
第6次结果
-5 6 8 6 11 33 88 666 
第7次结果
-5 6 8 6 11 33 88 666 
第1次结果
-5 6 8 6 11 33 88 666 
第2次结果
-5 6 8 6 11 33 88 666 
第3次结果
-5 6 6 8 11 33 88 666 
第4次结果
-5 6 6 8 11 33 88 666 
第5次结果
-5 6 6 8 11 33 88 666 
第6次结果
-5 6 6 8 11 33 88 666 
第7次结果
-5 6 6 8 11 33 88 666 
-5 6 6 8 11 33 88 666