数据结构——简单的希尔插入排序
简单的希尔插入排序
对int数组进行排序,也可自定义数据类型
环境 codeblocks 17 通过
code
// ChenYe 2018/12/05
#include <iostream>
#define MAXSIZE 1000
using namespace std;
int len; // 全局长度变量
void ShellInsert(int a[],int dk)
{// 按增量序列dt,对a[]进行1趟希尔排序
int i,j;
for(i=dk+1;i<len;i++) //执行n-1趟插入
if(a[i]<a[i-dk])
{
a[0] = a[i]; // 暂存
for(j=i-dk;j>0&&a[0]<a[j];j=j-dk) // 从后往前,记录后移找到插入位置
a[j+dk] = a[j];
a[j+dk] = a[0]; // 插入
}
}
void ShellSort(int a[], int dt[], int t)
{// 按增量序列dt[],对a[]进行t趟希尔排序
for(int k=0;k<t;k++)
ShellInsert(a,dt[k]); // 一趟增量为dt[k]的希尔插入排序
}
int main()
{
int num[MAXSIZE];
int n,i, key;
// 输入
for(n=1; n<MAXSIZE; n++) // 从下表1开始!!
{
cin>>key;
if(key==0)
break;
num[n] = key;
}
len = n;
int dt[]={5,3,1}; // 自定义的希尔排序增量,也可以根据len使用函数生成
ShellSort(num,dt,3); // 希尔排序
// output
for(i=1; i<n; i++)
{
cout<<num[i]<<" ";
}
return 0;
}
/*
test data:
输入:
7 4 3 5 2 1 8 9 0
输出:
1 2 3 4 5 7 8 9
*/