希尔排序实际上是一种特殊的插入排序,它是通过对直接插入排序的一些特点的利用,从而达到化简得效果。 具体内容为:
1.一方面,小段的直接插入排序,效率很高; 2.另一方面,当待排数据基本上是有序的时候,直接插入排序的效率也会很高; 利用这两个特点, 即可构成希尔排序。
注释在代码中
void Shell_Sort_Unit(Sqlit &L,int d)//d为比较增量
{
int j,k;
for(j=d+1;j<=L.length;j++)//length不包括哨兵
{
L.R[0]=L.R[j];
for(k=j-d;k>0&&L.R[0].key<L.R[k].key;k=k-d)
{
L.R[k+d]=L.R[k];
}
L.R[k+d]=L.R[0];
}
}
完整代码:
#include "stdafx.h"
#include "malloc.h"
#include "stdlib.h"
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define MAX_SIZE 100
#define TRUE 1
#define FLASE 0
typedef int KeyType;
typedef struct RecType
{
KeyType key;/*关键字*/
}RecType;
typedef struct Sqlist
{
RecType R[MAX_SIZE];
int length;
}Sqlist;
void Create(Sqlist &L)
{
int d = 0;
L.length = 10;
L.R[0].key= 0;
for (int i = 1; i <= 10; i++)
{
printf("请输入第%d个数据", i);
scanf_s("%d", &d);
L.R[i].key = d;
}
}
void Travel(Sqlist L)
{
for (int i = 1; i <= L.length; i++)
{
printf("节点%d的主键:%d\r\n", i, L.R[i].key);
}
}
/*希尔排序*/
void Shell_Sort_Unit(Sqlist &L, int d)
{
int c, j;
for (j = d + 1; j < L.length; j++)
{
L.R[0] = L.R[j];
for (c = j - d; c>0 && L.R[c].key > L.R[0].key; c = c - d)
{
L.R[c + d] = L.R[c];
}
L.R[c + d] = L.R[0];
}
}
void Shell_Sort(Sqlist &L, int dk[], int t)
{
for (int i = 0; i < t; i++)
{
Shell_Sort_Unit(L, dk[i]);
}
}
int main()
{
Sqlist L;
Create(L);
Travel(L);
int dk[3];
dk[0] = 5;
dk[1] = 3;
dk[2] = 1;
Shell_Sort(L, dk, 3);
Travel(L);
}
运行示意图:
全文结束,欢迎在评论区讨论~