文档介绍：排序算法详解
第1页，此课件共68页哦
问题的提出：
为什么要排序？有序表的优点？缺点？
构造关系。
按照什么原则排序？
比较？
如何进行排序？
第2页，此课件共68页哦
基本概念
排序（Sorting）：
记录个数，n<MAXNUM */
RecordNode *record;
}SortObject;
第11页，此课件共68页哦
直接插入排序算法复杂度评价
极端情况下：
最小比较次数∶每个记录仅比较一次
最大比较次数∶每个记录比较已排好序的记录长度
第12页，此课件共68页哦
直接插入排序算法评价2
最小移动次数∶
最大移动次数∶
第13页，此课件共68页哦
直接插入排序算法评价3
初始数据状态相关：
文件初态不同时，直接插入排序所耗费的时间有很大差异。
若文件初态为正序，则算法的时间复杂度为O(n)
若初态为反序，则时间复杂度为O(n2)
第14页，此课件共68页哦
直接插入排序算法评价4 —— 平均复杂度
插入记录Ri-1，有i种可能的插入位置，即插入到第0，1，…，i-1位置上，假设每种情况发生的概率是相等的，均为 pj = 1/i (j=0,1,…,i-1)
比较次数为Cj=j+1(j=0,…,i-2,i-2)，则插入记录Ri-1的平均比较次数为∶
第15页，此课件共68页哦
直接插入排序算法评价5 —— 平均复杂度
直接插入排序的
总的比较次数为：
第16页，此课件共68页哦
直接插入排序算法评价
直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)
直接插入排序的平均时间复杂度为T(n) = O(n2)
算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1)
直接插入排序是稳定的
第17页，此课件共68页哦
存储结构与算法优化
顺序存储结构：
二分插入算法，减少比较次数。
链式存储结构：
减少移动次数。
第18页，此课件共68页哦
二分法插入排序
特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序
限制：必须采用顺序存储方式。
第19页，此课件共68页哦
例：有6个记录，前5 个已排序的基础上，对第6个记录排序。
[ 15 27 36 53 69 ] 42
low mid high
[ 15 27 36 53 69 ] 42
low high
mid
[ 15 27 36 53 69 ] 42
high low
[ 15 27 36 42 53 69 ]
(high<low ，查找结束，插入位置为low 或high+1 )
( 42>36 )
( 42<53 )
第20页，此课件共68页哦
二分法插入排序算法
void binSort(SortObject * pvector)
{ int i, j, left, mid, right; RecordNode temp; for( i = 1; i < pvector->n; i++ ) { temp = pvector- >record[i]; left = 0; right = i – 1; while (left <= right) { mid = (left+right)/2；
if ( < vector->record[mid].key) right = mid-1;
else
left = mid+1;
}//while
for(j=i-1; j>=left; j--)
pvector->record[j+1] =