数据结构与算法课件作者张晓莉王苗第8章节_排序.ppt

数据结构 6. 记录和排序表的数据结构 在本章的讨论中，除特殊声明外，一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数*/ typedef struct { keytype key; /*关键码字段*/ …… /*其它信息*/ } datatype; /*记录类型*/ datatype R[MAXNUM]; /*定义排序表的存储*/ 如不加特别说明，排序表中的记录R1…Rn存放在R[1]…R[n]分量中，R[0]分量闲置或做监视哨（n是排序表中记录的个数）。 R[0] R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] R[9] R[10] 初始序列： 36 20 18 10 60 25 30 18 12 56 i=2 ： (20) 20 36 18 10 60 25 30 18 12 56 i=3 ： (18) 18 20 36 10 60 25 30 18 12 56 i=4 ： (10) 10 18 20 36 60 25 30 18 12 56 …… 【算法8-1】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的个数*/ for(i=2; i=n; i++) if (R[i].keyR[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中，R[0]为监测哨*/ for(j=i-1; R[0].keyR[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } } 【算法8-2】折半插入排序算法 void B_InsertSort(datatype R[ ], int n) { /* 对排序表R[1]..R[n]作折半插入排序, n是记录的个数*/ for(i=2; i=n; i++) { R[0]=R[i]; /* 保存待插入元素 */ low=1; high=i?1; /* 设置初始区间 */ while(low=high) /* 该循环语句完成确定插入位置 */ { mid=(low+high)/2; if(R[0].keyR[mid].key) low=mid+1; /* 插入位置在高半区中 */ else high=mid-1; /* 插入位置在低半区中 */ } for(j=i-1;j=high+1;j--) /* high+1为插入位置 */ R[j+1]=R[j]; /* 后移元素，留出插入空位 */ R[high+1]=R[0]; /* 将元素插入 */ } } 【算法8-3】表插入排序位置重排算法 void B_InsertSort(SNodeType R[ ],int n) { /*将按表插入排序方法已排好序的静态链表记录位置重排, n为记录个数*/ int i,j,p; /* j指当前重拍元素，i为应该到的位置*/ /* p指下一个待排元素的初始位置*/ datetype s; j=R[0].next; /*第一个元素的位置*/ R[0].n