衡量排序方法的标准 排序时所需要的平均比较次数 排序时所需要的平均移动 排序时所需要的平均辅助存储空间
衡量排序方法的标准 ▪ 排序时所需要的平均比较次数 ▪ 排序时所需要的平均移动 ▪ 排序时所需要的平均辅助存储空间
待排记录的数据类型定义为: #define maXsize 20 Typedef int Keytype pedef struct kEytYpe key; ∥关键字项 nfo Type otherinfo;∥其它数据项 BRedType Typedef struct RedType rMAXSIze+1/r0闲置或用作哨兵 int length; iSqlist;
待排记录的数据类型定义为： #define MAXSIZE 20 Typedef int KeyType Typedef struct {KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; Typedef struct {RedType r[MAXSIZE+1] //r[0]闲置或用作哨兵 int length; }Sqlist;
插入排序( Insert Sorting) 插入排序的基本方法是:每步将一个待排序的对 象,按其关键字大小,插入到前面已经排好序的 组对象的适当位置上,直到对象全部插入为止。 直接插入排序( nsert Sort 直接插入排序的基本思想是:当插入第i(≥1)个对象 时,前面的V10,Ⅵ,,v1已经排好序。这时,用 v引的关鍵字与叫l,v2],的关键字顺序进行比较 找到插入位置即将v插入,原来位置上之后的所有对 象依次向后顺移
插入排序 (Insert Sorting) 直接插入排序的基本思想是：当插入第i (i 1) 个对象 时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用 v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较， 找到插入位置即将v[i]插入，原来位置上之后的所有对 象依次向后顺移。 插入排序的基本方法是：每步将一个待排序的对 象，按其关键字大小，插入到前面已经排好序的 一组对象的适当位置上，直到对象全部插入为止。 直接插入排序 (Insert Sort)
各 趟 排 21 25//49 25 608 序 012345 结 果 =1目 49 25 6(8 25 2 3 5 temp 49 i=2 2125 08 012345 tem
各 趟 排 序 结 果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 25 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2
49 i=3 2125 608 25 012345 4同园回同 0123 5 temp 5同 21 252549 b 012345 tem
21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 i = 4 08 0 1 2 3 4 5 temp 21 25 49 16 25* 08 i = 5 i = 3 25* 16 08