第十章 内部排序案例.ppt

第十章 内部排序;主要内容;排序概念;;比较标准;基本操作;#define MAXSIZE 20 //一个用作示例的小顺序表的最大长度 typedef int KeyType; //定义关键字类型为整数类型 typedef struct { KeyType key; //关键字 InfoType otherinfo; //其它数据项 }RedType; //记录类型 typedef struct { RedType r[MAXSIZE+1]; //r[0]赋闲或用作哨兵单元 int length; //顺序表长度 }SqList;;10.2 插入排序;基本思想：顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置;;直接插入排序 ;void InsertSort(SqList L) { //对顺序表L做直接插入排序 for (i=2; i=L.length; ++i) if(LT(L.r[i].key, L.r[i-1].key)) {//将L.r[i]插入有序子表 L.r[0]=L.r[i]; for(j=i-1; LT(L.r[0].key, L.r[j].key); --j) L.r[j+1]=L.r[j]; //记录后移 L.r[j+1]=L.r[0]; //插入到正确位置 } }//InsertSort;;void BInsertSort(SqList L) { //对顺序表L做折半插入排序 for (i=2; i=L.length; ++i) { L.r[0]=L.r[i]; //将L.r[i]暂存到L.r[0] low=1; high=i-1; while(low=high) //在r[low..hight]中折半查找有序插入的位置 { m=(low+high)/2; if(LT(L.r[0].key, L.r[m].key)) high=m-1; else low=m+1; } //插入位置为hight+1 for(j=i-1;j=high+1; --j) L.r[j+1]=L.r[j]; //记录后移 L.r[high+1]=L.r[0]; //插入到正确位置 } }//BInsertSort;三、2-路插入排序;四、表插入排序 #define SIZE 100 //静态链表容量 typedef struct { RedType rc; //记录项 int next; //指针项 }SLNode; //表结点类型 typedef struct {SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 }SlinkListType; //静态链表类型 采用静态链表结构，令r[0]为表头结点， 且r[0].rc.key为MAXINT （1）将r[0]和r[1]构成一个循环链表 （2）将r[2]到r[n]依次插入循环链表;key:49 38 65 97 76 13 27 49;表插入排序只得到一个有序链表，只能进行顺序查找，不能随机查找和折半查找。 要进行折半查找，则需要重排记录：顺序扫描有序链表，将第i个结???移至数组的第i个分量中。 设SlinkListType SL; 第i个最小关键字的下标为p， （p的初值为r[0].next, 要求pi，否则依next继续找p,因为前i-1个数的位置已调整好） q=r[p].next; 互换r[p]和r[i]; r[i].next=p;;;void Arrange(SlinkListType SL) { //根据静态链表SL中各结点的指针调整记录位置， //使SL中的记录按关键字非递减有序顺序排列 p=SL.r[0].next; //p指示第一个记录的当前位置 for(i=1;iSL.length;++i) //SL.r[1..i-1]中记录已按关键字有序排列 //第i个记录在SL中的当前位置应不小于i { while(pi) p=SL.r[