插入排序
直接插入排序
直接插入排序是一个稳定的排序 算法时间复杂度$O(n^2)$
适用于顺序存储和链式存储
前提环境条件
在顺序表中对表内元素进行直接插入排序
对线性表·1描述的顺序表做了几处修改
顺序表创建从L.data[1]开始存储元素 L.data[0]不存储元素
顺序表遍历从L.data[1]到L.data[n] n为L.length表长
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
|
using namespace std;
typedef int ElemType;//排序必须是数字
typedef struct{
ElemType *data;
int length;
}SqList;
bool Initlist_Sq(SqList &L){//初始化顺序表L
L.data = new ElemType[MAXSIZE];
L.length = 0;
return 1;
}
bool ListInsert_Sq(SqList &L,int i,ElemType e){//插入表L
if((i<1)||(i>L.length+1)) return 0;
if(L.length==MAXSIZE) return 0;
for(int j=L.length;j>=i;j--){
L.data[j] = L.data[j-1];
}
L.data[i] = e;//从L.data[1]开始存储元素
L.length++;
return 1;
}
int GetLength(SqList L){//求表长
return (L.length);
}
int ShowList(SqList L){//遍历整个线性表的元素并输出
for(int i=1;i<=L.length;i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
|
直接插入排序代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool InsertSort(SqList &L,int n){//n为表长
int i,j;
for(i=2;i<=n;i++){
if(L.data[i]<L.data[i-1]){//第i个元素小于它前驱的元素
L.data[0]=L.data[i];//哨兵暂存i元素
for(j=i-1;L.data[0]<L.data[j];j--)//从后向前查找待插入的位置
L.data[j+1]=L.data[j];//将比L.data[0]大的元素都向后移位
L.data[j+1]=L.data[0]; //复制到插入位置
//L.data[0]比L.data[j]大 跳出循环 在L.data[j+1]插入L.data[0]
}
}
return 1;
}
|
折半插入算法
针对顺序存储的线性表 可以使用折半查找来确定待插入位置
折半插入排序是一种稳定的排序方法
折半插入排序相较于直接插入排序减少了比较元素的次数 约为$O(nlog_{2}n)$
比较元素次数取决于表中元素个数n
元素移动次数未改变 因此时间复杂度仍为$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool InsertSort(SqList &L,int n){//从小到大的递增顺序排序
int i,j,low,high,mid;
for(i=2;i<=n;i++){
L.data[0]=L.data[i];//L.data[0]暂存i位置的元素
low=1;high=i-1;//设置折半查找的范围
while(low<=high){
mid=(low+high)/2;
if(L.data[mid]>L.data[0]) high=mid-1;//查找左半区
else low=mid+1;//查找右半区
}
for(j=i-1;j>=high+1;j--)
L.data[j+1]=L.data[j];//后移元素 空出插入位置
L.data[high+1]=L.data[0];
}
return 1;
}
|
希尔排序
希尔排序又称为缩小增量排序 只适用于顺序存储的线性表
设置一个增量 增量为区间长度 一般选择表长的一半 一直减半到1
在这个增量下的所有元素进行排序 然后缩小增量 再对这个增量下的所有元素进行排序 直到增量为1 进行最后的排序
n在某个特定范围时 希尔排序的时间复杂度为$O(n^{1.3})$
最坏情况下 希尔排序的时间复杂度为$O(n^2)$
希尔排序可能会改变元素的相对次序 因此是一种不稳定的排序方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool ShellSort(SqList &L,int n){//希尔排序
int i,j,dk;
for(dk=n/2;dk>=1;dk=dk/2){//dk为区间大小 初值为表长的一半 dk可以自己设置
for(i=dk+1;i<=n;i++){
if(L.data[i]<L.data[i-dk]){
L.data[0]=L.data[i];
for(j=i-dk;j>0&&L.data[0]<L.data[j];j-=dk)//同一区间大小下的一组元素完全排序
L.data[j+dk]=L.data[j];
L.data[j+dk]=L.data[0];
}
}
for(int k=1;k<=L.length;k++){//一次dk排序后遍历表 观察元素排序变化
cout<<L.data[k]<<" ";
}
cout<<endl;
}
return 1;
}
|
For instance:
L表内元素为 96 36 -9 0 47 23 1 8 10 7 表长n为10 增量dk为5
第一次排序 L[1]与L[6]比较排序 L[2]与L[7]比较排序 L[3]与L[8]比较排序 L[4]与L[9]比较排序 L[5]与L[10]比较排序
L表内元素为 23 1 -9 0 7 98 36 8 10 47 增量dk为5/2=2
第二次排序 L[1] L[3] L[5] L[7] L[9]比较排序 L[2] L[4] L[6] L[8] L[10]比较排序
L表内元素为 -9 0 7 1 10 8 23 47 36 98 增量dk为2/2=1
第三次排序 十个元素同时比较排序
L表内元素为 -9 0 1 7 8 10 23 36 47 98 排序完毕
