前端之家收集整理的这篇文章主要介绍了
shell排序及两种优化,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
原博客:@L_403_0@
//最佳步长: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