数据结构第十章内部排序之插入排序

谁践踏了优雅 2022-08-22 11:25 195阅读 0赞

PS:后面的元素的数值比前面的元素的小就插入

1.直接插入排序

\#include <stdio.h>  
\#define MAXSIZE 20 //定义一个顺序表最大长度为20  
\#define LH(a,b) ((a)<(b)) //定义LH(a,b)就是a<b  
typedef int KeyType; //定义关键字类型为整型，当然也可以是结构体之类的  
typedef struct  
\{  
KeyType key; //这里没有其他数据项，只有一项关键字  
\}RedType;  
  
typedef struct  
\{  
RedType r\[MAXSIZE+1\];//申请MAXSIZE个内存空间，r\[0\]闲置或者是用来做哨兵单元  
int length; //顺序表长度  
\}SqList; //定义一个顺序表  
  
  
void InsertSort(SqList &L)  
\{  
int i,j,k;  
 for(i=2;i<=L.length;i++)//从第二个元素开始和前面的元素比较  
\{  
if(L.r\[i\].key<L.r\[i-1\].key)//如果当前的元素关键字小于它的前一个元素的关键字  
\{  
L.r\[0\]=L.r\[i\];//将这个元素做哨兵，即将值赋给r\[0\],此时可以看成当前元素的位置

//是空的  
L.r\[i\]=L.r\[i-1\];//于是将前一个元素往后移一个位  
 for(j=i-2;LH(L.r\[0\].key,L.r\[j\].key);j--)//从第i个元素的前面的前面开始循环比较，找 //到适合的插入位置  
L.r\[j+1\]=L.r\[j\]; //循环后移  
L.r\[j+1\]=L.r\[0\];//最后将哨兵记录的值插入  
\}  
\}  
\}  
  
  
int main()  
\{  
SqList L;  
int i;  
scanf("%d",&L.length);  
for(i=1;i<=L.length;i++)  
scanf("%d",&L.r\[i\].key);  
InsertSort(L);  
return 0;  
\}

算法优劣分析：

两个for循环中，最坏情况下比较次数约为n，移动次数约为n，所以时间复杂度为O(n²)

2.折半插入排序

void BInsertSort(SqList &L)  
\{  
int i,j,k,low,high,m;  
for(i=2;i<=L.length;i++)//从第二个元素开始比较  
\{  
L.r\[0\]=L.r\[i\]; //将值赋给哨兵  
low=1;  
high=i-1; //初始定义low和high  
while(low<=high) 在r\[low..high\]中查找元素插入的位置  
\{  
m=(low+high)/2;  
if(LH(L.r\[0\].key,L.r\[m\].key)) //确定插入点在高半区还是低半区，然后折半继续直 //到low>high时停止  
high=m-1;  
else low=m+1;  
\}  
for(j=i-1;j>=high+1;j--) //只能在前面插入  
L.r\[j+1\]=L.r\[j\]; //循环后移  
L.r\[high+1\]=L.r\[0\];  
\}  
\}  
int main()  
\{  
SqList L;  
int i;  
scanf("%d",&L.length);  
for(i=1;i<=L.length;i++)  
scanf("%d",&L.r\[i\].key);  
BInsertSort(L);  
return 0;  
\}

3.希尔排序

基本思想：现将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。

通过间隔分组的方法构建子序列，即是将相隔某个“增量”的元素构成一个子序列。

\#include <stdio.h>  
\#define MAXSIZE 20  
\#define LH(a,b) ((a)<(b))  
typedef int KeyType;  
typedef struct  
\{  
KeyType key;  
\}RedType;  
typedef struct  
\{  
RedType r\[MAXSIZE+1\];  
int length;  
\}SqList;  
//同上  
  
void ShellInsert(SqList &L,int dk)  
\{  
int i,j;  
for(i=dk+1;i<=L.length;i++)  
\{  
if(LH(L.r\[i\].key,L.r\[i-dk\].key))//如果第i-dk个元素比第i个元素大  
\{

L.r\[0\]=L.r\[i\];  
for(j=i-dk;j>0&&LH(L.r\[0\].key,L.r\[j\].key);j-=dk)  
L.r\[j+dk\]=L.r\[j\];  
L.r\[j+dk\]=L.r\[0\];  
\}  
\}  
\}  
  
  
void ShellSort(SqList &L,int dlta) //分子序列函数  
\{  
int m=1,k;  
for(;dlta>=1&&m;dlta=dlta/2)  
\{  
if(dlta==1) //如果dlta为1则证明表中只有两个元素  
m=0; //控制当只有两个元素时只循环一次  
ShellInsert(L,dlta);  
\}  
\}  
  
int main()  
\{  
SqList L;  
int i;  
int dk=L.length/2; //增量为表长的一半  
scanf("%d",&L.length);  
for(i=1;i<=L.length;i++)  
scanf("%d",&L.r\[i\].key);  
ShellSort(L,L.length/2);  
return 0;  
\}