数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）

118 阅读 0 评论 78 点赞

我是靠谱客的博主义气冰棍，这篇文章主要介绍数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定），现在分享给大家，希望可以做个参考。

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

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 基本实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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. 质数-----> 用途广泛（加密算法等）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#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);
}

结果

复制代码

1
2
3
4
797161
shell Ksort time =430303 clock
SortLib time =716167 clock
shell sort time =616954 clock

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

复制代码

1
2
3
4
5
6
shell Ksort time =3524 clock
// Kunth 序列
SortLib time =4869 clock
// 系统库
insert sort time =1300953 clock
//插入排序

最后

以上就是义气冰棍最近收集整理的关于数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）的全部内容，更多相关数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：笔记
浏览次数：118 次浏览
发布日期：2023-12-20 11:55:35
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_2_f1_14_z_26_2.html

数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）

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

1.简介

1.1 基本实现

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

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

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

最后

评论列表共有 0 条评论

发表评论取消回复

数据结构与算法7---希尔排序希尔排序---基于插入排序（性能比插入排序好，但不稳定）

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

1.简介

1.1 基本实现

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

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

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

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

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

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

发表评论取消回复