数据结构C语言版插入排序

时间：2024.5.15

#include <stdio.h>

#include <malloc.h>

数据结构C语言版插入排序

P265-P272 编译环境：VC++6.0

日期：20xx年2月16日

typedef int KeyType;

typedef int InfoType;

// 记录类型

typedef struct

{

KeyType key; // 关键字项

InfoType otherinfo; // 其它数据项

}RedType;

#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度

// 顺序表类型

typedef struct

{

RedType r[MAXSIZE+1]; int length; // r[0]闲置或用作哨兵单元 // 顺序表长度 // 定义关键字类型为整型 // 定义其它数据项的类型

}SqList;

// 打印顺序表

void print(SqList L)

{

int i;

}

算法10.1 P265

对顺序表L作直接插入排序。 for(i = 1; i <= L.length; i++) printf("(%d, %d) ", L.r[i].key, L.r[i].otherinfo); printf("\n\n");

void InsertSort(SqList *L) {

int i, j;

// 升序排序 for( i = 2; i <= (*L).length; ++i) if((*L).r[i].key < (*L).r[i-1].key) {

} (*L).r[0] = (*L).r[i]; // 复制为哨兵 for(j = i-1; (*L).r[0].key < (*L).r[j].key; --j) (*L).r[j+1]=(*L).r[j]; // 记录后移 // 插入到正确位置 (*L).r[j+1] = (*L).r[0]; print(*L); // 打印线性表

}

算法10.2 P267

对顺序表L作折半插入排序。 */

void BInsertSort(SqList *L) {

int i,j,m,low,high;

for(i = 2; i <= (*L).length; ++i) { (*L).r[0] = (*L).r[i]; // 将L.r[i]暂存到L.r[0] low = 1; high = i-1; // 在r[low..high]中折半查找有序插入的位置 while(low <= high) { } m = (low + high) / 2; // 折半 if((*L).r[0].key < (*L).r[m].key) 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]; print(*L); // 记录后移 // 插入

// 2路插入排序 P267

void P2_InsertSort(SqList *L) {

int i,j,first,final; RedType *d; // 生成L.length个记录的临时空间 d = (RedType*)malloc((*L).length*sizeof(RedType)); // 设L的第1个记录为d中排好序的记录(在位置[0]) d[0] = (*L).r[1]; // first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 first = final = 0; for(i = 2; i <= (*L).length; ++i) { // 依次将L的第2个～最后1个记录插入d中 if((*L).r[i].key < d[first].key) { /* } else if((*L).r[i].key > d[final].key) { /* 待插记录大于d中最大值，插到d[final]之后(不需移动d数组的元素) */ final=final+1; 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素) */ first = (first - 1 + (*L).length) % (*L).length; // 设d为循环向量 d[first] = (*L).r[i];

d[final]=(*L).r[i]; } else { /* } 待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素) // 移动d的尾部元素以便按序插入记录 */ j = final++; { } while((*L).r[i].key < d[j].key) d[(j+1)%(*L).length] = d[j]; j = (j-1+(*L).length) % (*L).length; d[j+1] = (*L).r[i]; } // 把d赋给L.r, 线性关系 for(i = 1;i <= (*L).length; i++)

(*L).r[i] = d[(i+first-1)%(*L).length];

}

// 算法10.4 P272

// 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比， // 作了以下修改：

// 1.前后记录位置的增量是dk,而不是1;

// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。 void ShellInsert(SqList *L,int dk)

{

int i,j;

for(i=dk+1;i<=(*L).length;++i) if ((*L).r[i].key < (*L).r[i-dk].key) { } // 需将(*L).r[i]插入有序增量子表 (*L).r[0]=(*L).r[i]; // 暂存在(*L).r[0] for(j=i-dk;j>0&&((*L).r[0].key < (*L).r[j].key);j-=dk) (*L).r[j+dk]=(*L).r[j]; // 记录后移，查找插入位置 (*L).r[j+dk]=(*L).r[0]; // 插入

}

// 算法10.5 P272

// 按增量序列dlta[0..t-1]对顺序表L作希尔排序。 void ShellSort(SqList *L,int dlta[],int t) {

int k;

for(k=0;k<t;++k)

}

#define N 8

#define T 3

int main()

{

/*************测试直接插入排序*******************/ #if 0

printf("\n直接插入排序的过程\n");

InsertSort(&L); RedType d[N] = { { 49, 1}, { 38, 2}, { 65, 3}, { 97, 4}, { 76, 5}, { 13, 6}, { 27, 7}, { 49, 8} }; SqList L; int i; int dt[T] = { 5, 3, 1}; // 增量序列数组 // 给L.r赋值 for(i = 0; i < N; i++) L.r[i+1]=d[i]; L.length = N; printf("排序前:\n"); print(L); { } ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序 printf("第%d趟排序结果: ",k+1); print(*L);

printf("\n直接插入排序后:\n");

print(L);

#endif

/*************测试折半插入排序*******************/

#if 0

printf("\n折半插入排序的过程\n");

/*************测试2路插入排序*******************/

#if 0

P2_InsertSort(&L);

printf("\n2路插入排序后:\n"); BInsertSort(&L); printf("\n折半插入排序后:\n"); print(L); #endif

print(L);

#endif

/*************测试希尔排序*******************/

#if 0

ShellSort(&L,dt,T); printf("\n希尔排序后:\n"); print(L);

#endif

system("pause");

return 0;

}

输出效果：

*************测试直接插入排序*******************

排序前:

(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

直接插入排序的过程

(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

(38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (13, 6) (27, 7) (49, 8)

(13, 6) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (27, 7) (49, 8)

(13, 6) (27, 7) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (49, 8)

(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)

直接插入排序后:

(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)

请按任意键继续. . .

*************测试折半插入排序*******************

排序前:

(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

折半插入排序的过程

(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

(38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (13, 6) (27, 7) (49, 8)

(13, 6) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (27, 7) (49, 8)

(13, 6) (27, 7) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (49, 8)

(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)

折半插入排序后:

(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)

请按任意键继续. . .

*************测试2路插入排序*******************

排序前:

(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

2路插入排序后:

(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)

请按任意键继续. . .

*************测试希尔排序*******************

排序前:

(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

第1趟排序结果: (13, 6) (27, 7) (49, 8) (97, 4) (76, 5) (49, 1) (38, 2) (65, 3)

第2趟排序结果: (13, 6) (27, 7) (49, 8) (38, 2) (65, 3) (49, 1) (97, 4) (76, 5)

第3趟排序结果: (13, 6) (27, 7) (38, 2) (49, 8) (49, 1) (65, 3) (76, 5) (97, 4)

希尔排序后:

(13, 6) (27, 7) (38, 2) (49, 8) (49, 1) (65, 3) (76, 5) (97, 4)

请按任意键继续. . .

第二篇：C语言版数据结构希尔排序

2. 希尔排序

详细设计

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

typedef int KeyType;

typedef int OtherType;

#define Max_Size 5000

typedef struct

{

KeyType key;

OtherType other_data;

}RecordType;

void ShellInsert(RecordType r[], int length, int delta)

/*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/

{

int i,j;

for(i=1+delta;i<=length;i=i+delta) //1+delta为第一个子序列的第二个元素的下标 if(r[i].key<r[i-delta].key) { RecordType t; t=r[i]; //备份r[i] } for(j=i;j>0 && t.key<r[j-delta].key;j-=delta) r[j]=r[j-delta]; r[j]=t;

}/*ShellInsert*/

void ShellSort(RecordType r[], int length, int delta[], int n)

/*对记录数组r做希尔排序，length为数组r的长度，delta 为增量数组，n为delta[]的长度 */

{

for(int i=0;i<n;++i)

ShellInsert(r,length,delta[i]);

}

void main()

{

int i; RecordType r[Max_Size]; int len;

int delta[4]={6,4,2,1}; printf("请输入待排序记录的长度:"); scanf("%d",&len); srand((unsigned)time(NULL)); for(i=1;i<=len;i++) r[i].key =rand(); printf("\n待排序记录:\n"); for(i=1;i<=len;i++) printf("%6d ",r[i].key); printf("\n"); ShellSort(r,len,delta,4); printf("\n排序后的记录:\n"); for(i=1;i<=len;i++) printf("%6d ",r[i].key); printf("\n\n");

}

测试结果

C语言版数据结构希尔排序

更多相关推荐：

c语言数据结构总结: 数据结构大全一概论二线性表三栈和队列四串五多维数组和广义表十文件六树七图八排序九查找1一概论1评价一个算法时间性能的主要标准是算法的时间复杂度2算法的时间复杂度与问题的规模有关外还与输入实例的初始状态有关3一般...
c语言数据结构总结: 附录实验源程序实验一线性表操作程序1顺序存储的线性表和运算includeltstdiohgtdefineMAXSIZE100intlistMAXSIZEintninsertinaseqlistintsqinse...
《数据结构(C语言版)-清华大学出版社》复习总结(视频+课本+截图) (1): 本资料由网友IOU_520JRForever整理提供，仅供参考，如有好的建议或意见请与编者联系，谢谢！第一章绪论视频为数据结构1&2。同步教学视频下载：数据结构1：http://v.youku.com/v_sh…
《数据结构(C语言版)-清华大学出版社》复习总结(视频+课本+截图) (2): 数据结构C语言版清华大学出版社复习总结视频课本截图本资料由网友IOU520JRForever整理提供仅供参考如有好的建议或意见请与编者联系谢谢第二章线性表视频为数据结构3amp4amp5amp638分钟同步教学...
数据结构C语言版部分习题及答案: 国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法11算法算法是指解题方案的准确而完整的描述算法不等于程序也不等计算机方法程序的编制不可能优于算法的设计算法的基本特征是一组严谨地定义运算顺序的规则...
数据结构教案C语言版: 课程教案课程名称数据结构授课教师学习对象任课时间一学生情况分析数据结构是计算机专业的一门核心专业课程学生在前期的学习中已经学习了C语言程序设计课程通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力二...
数据结构c语言版期末考试复习试题: 数据结构与算法复习题一选择题1在数据结构中从逻辑上可以把数据结构分为CA动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构2数据结构在计算机内存中的表示是指A数据的存储结构B数据...

c语言、数据结构中的8种排序分析与代码: 8种排序一冒泡排序小者上扬原则已知一组无序数据a1a2an需将其按升序排列首先比较a1与a2的值若a1大于a2则交换两者的值否则不变再比较a2与a3的值若a2大于a3则交换两者的值否则不变再比较a3与a4以此类...
数据结构C语言版: includeltstdiohgtdefineINF1000defineMAXVERTEXNUM20typedefenumDGDNUDGUDNGraphKindtypedefstructArcCellintadjintinfoAr...
数据结构C语言版期末考试试题(有答案): 路就在你脚下只要走就能到达远方quot数据结构quot期末考试试题一单选题每小题2分共12分1在一个单链表HL中若要向表头插入一个由指针p指向的结点则执行AHLpsp一gtnextHLBp一gtnextHLHL...

《数据结构(C语言版) 》课程综合性实验报告: 华北科技学院计算机系综合性实验实验报告课程名称数据结构C语言版实验学期20xx至20xx学年第2学期学生所在系部计算机系年级大二专业班级信管B081学生姓名尹芳学号20xx07034113任课教师兰芸实验成绩计...
数据结构实验报告(C语言)(强力推荐): 数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查找和排序技术让我们在实际上机中具有编制相当规模的程序的能力养成一种良好的程序设计...

热门关注

数据结构C语言版 插入排序

第二篇：C语言版数据结构 希尔排序

数据结构C语言版插入排序

第二篇：C语言版数据结构希尔排序