每天一种算法-希尔排序

╰+哭是因爲堅強的太久メ 2022-08-21 09:43 115阅读 0赞

希尔排序就是 插入排序。是反复只用插入排序的结果。  
因为插入排序，只是前后的元素进行比较，当序列很长的时候，效率会很低。  
希尔排序假设一个h, 比较间隔为h的元素的大小。让需要移动的元素，每次可以移动尽量多的距离。然后逐步缩小h的取值。最后h会缩小到1。 这时候就完全是插入排序了。

Java实现

package bigo;
    
    public class insert {
    
        static void hill_sort(int src[], int len)
        {
            int h=1;
            while(h<len/3){
                h = h*3+1;
            }
            while(h>=1){
                for(int i=h;i<len;i++){
                    for(int j=i; j-h>=0 && src[j] < src[j-h] ; j-=h)
                    {
                        int tmp=src[j];
                        src[j]=src[j-h];
                        src[j-h]=tmp;
                    }
                }
                h = h/3;
            }
    
        }
    
        public static void main(String[] args) {
            int src[] = {
       9,7,5,45,3,23,2,12,1};
            hill_sort(src, src.length);
            //insert_sort(src, src.length);
            for (int i = 0; i < src.length; i++) {
                System.out.println(src[i]);
            }
        }
    }

c++实现

#include <iostream>
    
    using namespace std;
    void shell_sort(int src[], int len)
    {
        int h=1;
        while(h<len/3)
            h = h*3+1;
    
        while(h>=1){
            for(int i=h;i<len;i++)
            {   
                for(int j=i; j>=h && src[j]<src[j-h]; j=j-h)
                    swap(src[j],src[j-h]);
            }   
    
            h=h/3;
        }   
    
    }
    
    int main()
    {
        int src[] = {
       8,7,6,5,3,2,1,0};
        int len=sizeof(src)/sizeof(int);
        shell_sort(src,len);
    
        for(int i=0;i<len;i++)
            cout << src[i] << endl;
    
    }