09_排序课案.pptx

第九章 排序;概述 插入排序 交换排序 选择排序 归并排序 基数排序;概述;排序算法的稳定性: 如果在元素序列中有两 个元素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面。如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。;排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。 算法执行时所需的附加存储: 评价算法好坏的另一标准。;插入排序 (Insert Sorting);i;template class T void dataListT::InsertionSort(dataListT list) {//按关键妈key非递减顺序对表进行排序 for(int i=1;ilist.currentSize;i++) Insert(list,i); } template class T void dataListT::Insert(dataListT list,int i) {//将元素list.Vector[i]按其关键码插入到有序表list.Vector[0]...list.Vector[i-1]中，使得list.Vector[0]...list.Vector[i]有序 ElementT temp=list.Vector[i];int j=i; while(j0 temp.keylist.Vector[j-1].key) { list.Vector[j]=list.Vector[j-1];j--; } list.Vector[j]=temp; }; 基本思想是 : 设在顺序表中有一 个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的元素。在插入V[i] 时, 利用折半有哪些信誉好的足球投注网站法寻找V[i] 的插入位置。 折半插入排序的算法 template class T void BinaryInsertSort(dataListT list) {//按关键妈key非递减顺序对表进行排序 for(int i=1;ilist.currentSize;i++) BinaryInsert(list,i); };template class T void BinaryInsert(dataListT list,int i) {//利用折半查找，按list.Vector[i].key在list.Vector[0]...list.Vector[i-1]中查找list.Vector[i]应插入的位置，再空出这个位置进行插入 int left=0,right=i-1; ElementT temp=list.Vector[i]; while(left=right) {//利用折半查找插入位置 int middle=(left+right)/2;//取中点 if(temp.keylist.Vector[middle].key)//插入值小于中点值 right=middle-1;//向左缩小区间 else left=middle+1;//向右缩小区间 } for(int k=i-1;k=left;k--) list.Vector[k+1]=list.Vector[k];//成块移动空出插入位置 list.Vector[left]=temp;//插入 }; 算法分析 折半有哪些信誉好的足球投注网站比顺序有哪些信誉好的足球投注网站快, 所以折半插入排序就 平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第 i 个元素时，需要经过 ?log2i? +1 次排序码比较, 才能确定它应插入的位置。因此，将 n 个元素(为推导方便, 设为 n=2k ) 用折半插入排序所进行的排序码比较次数为： 折半插入排序是一个稳定的排序方法。;当 n 较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。 在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的元素移动次数与直接插入排序相同，依赖于元素