shell排序及两种优化

前端之家收集整理的这篇文章主要介绍了shell排序及两种优化前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

博客白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

//最佳步长:https://zh.wikipedia.org/wiki/希尔排序

#include <iostream>
#include <vector>
using namespace std;

void shellsort(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2){
        for(int i=0;i<step;++i){//1
            for(int j=i+step;j<n;j+=step){//2
                //在当前层做插入排序,相当于直接插入排序的第一种优化。见直接插入排序。
                if(vi[j]<vi[j-step]){//如果前一元素大于当前的元素
                    int temp=vi[j];
                    int k=j-step;
                    while(k>=0 && vi[k]>temp){
                        vi[k+step]=vi[k];
                        k=k-step;
                    }
                    vi[k+step]=temp;
                }
            }
        }
    }
}
//优化1:结构上的优化,shellsort中1与2处的for可以合并一下。
void shellsort1(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2){
        for(int j=step;j<n;++j){
            if(vi[j]<vi[j-step]){
                int temp=vi[j];
                int k=j-step;
                while(k>=0 && vi[k]>temp){
                    vi[k+step]=vi[k];
                    k=k-step;
                }
                vi[k+step]=temp;
            }
        }
    }
}
//优化2:结构上的优化,用swap来使代码更精简,但是效率会变低一点
void shellsort2(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2)
        for(int j=step;j<n;++j)
            for(int k=j-step;k>=0 && vi[k]>vi[k+step];k-=step)
                swap(vi[k],vi[k+step]);
}

int main(){
    vector<int> vi;
    vi={1,8,2,3,7,6,9,5,4};
//    shellsort(vi);
//    shellsort1(vi);
    shellsort2(vi);
    for(auto ieh: vi)
        cout<<ieh<<" ";
    cout<<endl;
    return 0;
}
原文链接:https://www.f2er.com/bash/391951.html

猜你在找的Bash相关文章