希尔排序c++实现(数据结构)

以下为按照数据结构教程正确编写且注释丰富的希尔排序实现案例:

#include<iostream> #include <string> #define error 0 #define ok 1 using namespace std; #define MAXSIZE 200 typedef int Key; typedef struct { Key key; string name; }Student; typedef struct { Student r[MAXSIZE + 1]; //数组 int length; //数组长度 }SqList; //-----------------以上为定义类型, 宏

void Init_sq(SqList& sq); //初始化 int Insert(SqList& sq, int i, Student s); //插入

void ShellSort(SqList& L); //希尔排序主程序 void ShellInsert(SqList& sq, int dk); //希尔排序遍历程序 //--------------以上1,2为链表基本操作声明 3,4为希尔排序函数声明

int main() { SqList sq; Init_sq(sq); Student sq0 = { 11,"bai" }; Student sq1 = { 22,"cai" }; Student sq2 = { 33,"dai" }; Student sq3 = { 44,"ear" };

Insert(sq, 1,sq0); Insert(sq, 2, sq1); Insert(sq, 2, sq2); Insert(sq, 1, sq3);

for (int i = 1; i <= sq.length; i++) { cout <<"原来每个元素:" << sq.r[i].key << sq.r[i].name << endl; } cout <<"sq.length:" << sq.length << endl;

ShellSort(sq); cout << "希尔插入排序:" << endl; for (int i = 1; i <= sq.length; i++) { cout << sq.r[i].key << sq.r[i].name << endl; } } //-----------------以上为主程序/测试程序

//链表初始化 void Init_sq(SqList &sq){ for (int i = 0; i < MAXSIZE + 1; i++) { sq.r[i].key = 0; sq.r[i].name = "bai"; } sq.length = 0; } //链表插入 int Insert(SqList& sq, int i,Student s) { //0不存储元素, 索引为1就是第一个元素 length代表实际长度 if (i<1 || i>MAXSIZE) { return error; }if (sq.length == MAXSIZE) { return error; } for (int j = sq.length ; j > i - 1; j--) //这时在最后一个j=i { sq.r[j + 1] = sq.r[j]; } sq.r[i] = s; sq.length++; return ok; } // 希尔排序主函数 void ShellSort(SqList& L) { //希尔排序主函数 int num; cout << "请输入希尔序列长度:" << endl; // n为增量序列最大值 + 1 cin >> num; int dk[5]; // //dk存储增量序列(0,1,2...), 这里需要手动修改数组长度,如果为了封装性.可以将数组和num都放到参数中 cout << "请输入" << num << "个增量序列,要递减且互质且最后一个为1:" << endl; for (int k = 0; k < num; k++) { cin >> dk[k]; }

for (int j = 0; j < num; j++) { cout << "增量为:" << dk[j]<< endl; ShellInsert(L, dk[j]); //每调用一次就按照一次不同的增量间隔进行希尔排序

} }

//希尔函数被调程序 void Shevoid ShellInsert(SqList& sq, int dk) { //这里除了间隔不同以外 就是普通的插入排序了

int i, j;

for (i = dk + 1; i < sq.length; i++) { //对每个元素排序

if (sq.r[i].key < sq.r[i - 1].key) { //如果i不是最大值 开始排序

sq.r[0] = sq.r[i]; //哨兵

for (j = i - dk; sq.r[0].key < sq.r[j].key; j = j - dk) {

sq.r[j + dk] = sq.r[j]; //后移

}

sq.r[j + dk] = sq.r[0];

//for结束时 返回j就是

}

}

}