目录

希尔排序---基于插入排序（性能比插入排序好，但不稳定）

1.简介

1.1 基本实现

1.2  gap的选择和位运算优化： gap 一般选 数组长度1/2

1.3 gap的选择

1.4 耗时比较  shell  Knuth序列 性能比sort函数查一倍

希尔排序---基于插入排序（性能比插入排序好，但不稳定）

1.简介

特点： 间隔大，移动次数少； 间隔小移动距离短。 （比普通插入排序效率好，但不稳定）

算法特点： 最优 n^1.3  最差n^2   最好 n   空间复杂度O（1） 不稳定

1.1 基本实现

#include<iostream>
#include<ctime>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
class InsertSort{
public:
InsertSort(){};
~InsertSort(){};
int sort(vector<int>&arr){
//gap =1 is InsertSort
int gap =4;
for(; gap>0; gap/=2){
for(int i=gap; i<arr.size(); i++){
for(int j=i; j>gap-1; j-=gap){
if(arr[j]<arr[j-gap]){
swap(arr[j],arr[j-gap]);
}else{
break;
}
}
}
}
return 0;
};
void mov(vector<int> &arr,int index ,int end){
int tmp = arr[end];
for(int i=end; i>index; --i){
arr[i]=arr[i-1];
}
arr[index]= tmp;
}
void GenRandArr(vector<int> &arr)
{
srand(time(0));
for(int i=0; i<arr.size(); ++i){
arr[i]=rand()%10;
}
};
void print(const vector<int> &arr)
{
for(int i=0; i<arr.size(); ++i){
cout<< arr[i]<<" ";
}
cout<<endl;
}
void compare(vector<int>& arr1, vector<int>&arr2)
{
for(int i=0; i<arr1.size(); ++i)
{
if(arr1[i]!=arr2[i]){
cout<<"compare wrong" <<endl;
return;
}
}
cout<<"compare right"<<endl;
};
private:
void swap(int &a ,int&b){
int tmp =a;
a =b;
b= tmp;
};
};
bool cmp(const int &a ,const int &b){
return (a<b);
}
#define ARR_SIZE 20
int main(){
vector<int> arr1(ARR_SIZE);
vector<int> arr2(ARR_SIZE);
InsertSort Ins;
Ins.GenRandArr(arr1);
Ins.print(arr1);
memcpy((void*)&arr2[0],(void*)&arr1[0], ARR_SIZE*sizeof(int));
Ins.print(arr2);
sort(arr2.begin(), arr2.end() ,cmp);
Ins.sort(arr1);
Ins.print(arr1);
Ins.print(arr2);
Ins.compare(arr1,arr2);
}

1.2  gap的选择和位运算优化： gap 一般选 数组长度1/2

int sort(vector<int>&arr){
//gap =1 is InsertSort
int gap = arr.size()>>1;
for(; gap>0; gap=gap>>1){
for(int i=gap; i<arr.size(); i++){
for(int j=i; j>gap-1; j-=gap){
if(arr[j]<arr[j-gap]){
swap(arr[j],arr[j-gap]);
}else{
break;
}
}
}
}
return 0;
};

1.3 gap的选择优化-->提高性能

适合中型排序

1.Knuth序列

Knuth序列： h=1  h=3h+1 

gap =(gap-1)/3

2. 质数-----> 用途广泛（加密算法等）

int sort(vector<int>&arr){
//gap =1 is InsertSort
int h=1 ;
while(h<arr.size()/3){ h = 3*h+1;}
int gap = h;
cout<< gap<<endl;
for(; gap>0; gap=(gap-1)/3){
for(int i=gap; i<arr.size(); i++){
for(int j=i; j>gap-1; j-=gap){
if(arr[j]<arr[j-gap]){
swap(arr[j],arr[j-gap]);
}else{
break;
}
}
}
}
return 0;
};

1.4 耗时比较  shell  Knuth序列 性能比sort函数快一倍， 原shell排序比sort函数快一点点

性能测试

#include<iostream>
#include<ctime>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
class InsertSort{
public:
InsertSort(){};
~InsertSort(){};
int sort(vector<int>&arr){
//gap =1 is InsertSort
int gap = arr.size()>>1;
for(; gap>0; gap=gap>>1){
for(int i=gap; i<arr.size(); i++){
for(int j=i; j>gap-1; j-=gap){
if(arr[j]<arr[j-gap]){
swap(arr[j],arr[j-gap]);
}else{
break;
}
}
}
}
return 0;
};
int K_sort(vector<int>&arr){
//gap =1 is InsertSort
int h=1 ;
while(h<arr.size()/3){ h = 3*h+1;}
int gap = h;
cout<< gap<<endl;
for(; gap>0; gap=(gap-1)/3){
for(int i=gap; i<arr.size(); i++){
for(int j=i; j>gap-1; j-=gap){
if(arr[j]<arr[j-gap]){
swap(arr[j],arr[j-gap]);
}else{
break;
}
}
}
}
return 0;
};
void mov(vector<int> &arr,int index ,int end){
int tmp = arr[end];
for(int i=end; i>index; --i){
arr[i]=arr[i-1];
}
arr[index]= tmp;
}
void GenRandArr(vector<int> &arr)
{
srand(time(0));
for(int i=0; i<arr.size(); ++i){
arr[i]=rand()%10;
}
};
void print(const vector<int> &arr)
{
for(int i=0; i<arr.size(); ++i){
cout<< arr[i]<<" ";
}
cout<<endl;
}
void compare(vector<int>& arr1, vector<int>&arr2)
{
for(int i=0; i<arr1.size(); ++i)
{
if(arr1[i]!=arr2[i]){
cout<<"compare wrong" <<endl;
return;
}
}
cout<<"compare right"<<endl;
};
private:
void swap(int &a ,int&b){
int tmp =a;
a =b;
b= tmp;
};
};
bool cmp(const int &a ,const int &b){
return (a<b);
}
#define ARR_SIZE 2000000
int main(){
vector<int> arr1(ARR_SIZE);
vector<int> arr2(ARR_SIZE);
vector<int> arr3(ARR_SIZE);
clock_t t;
long sec;
InsertSort Ins;
Ins.GenRandArr(arr1);
// Ins.print(arr1);
memcpy((void*)&arr2[0],(void*)&arr1[0], ARR_SIZE*sizeof(int));
memcpy((void*)&arr3[0],(void*)&arr1[0], ARR_SIZE*sizeof(int));
//Ins.print(arr2);
t =clock();
Ins.K_sort(arr3);
sec = (clock()-t);
cout<<"shell Ksort time =" <<sec<<" clock"<<endl;
t =clock();
sort(arr2.begin(), arr2.end() ,cmp);
sec = (clock()-t);
cout<<"SortLib time ="<< sec<<" clock"<<endl;
t =clock();
Ins.sort(arr1);
sec = (clock()-t);
cout<<"shell sort time =" <<sec<<" clock"<<endl;
//Ins.print(arr1);
//Ins.print(arr2);
// Ins.compare(arr1,arr2);
}

结果

797161
shell Ksort time =430303 clock
SortLib time =716167 clock
shell sort time =616954 clock

shell 排序比系统提供的库快一点

shell Ksort time =3524 clock
// Kunth 序列
SortLib time =4869 clock
// 系统库
insert sort time =1300953 clock
//插入排序

最后

以上就是义气冰棍为你收集整理的数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）的全部内容，希望文章能够帮你解决数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。