数据结构第20次课-排序A.ppt

《数据结构第20次课-排序A.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.6小结(各类排序方法比较）第9章排序1第九章排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序2按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(nlog2n)排序基本操作比较两个关键字大小

2、将记录从一个位置移动到另一个位置排序的稳定性排序的记录序列中可能存在两个或两个以上的关键字相等的记录，如果在排序前的序列里Ri领先于Rj（i

3、761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj97)7665493827(13273849657697)排序结果：6直接插入排序算法voidstraisort(intr[],intn){inti,j;for(i=2;i<=n;i++)//从第二个元素开始插入{r[0]=r[i];//哨兵设置1次移动j=i-1;while(r[0]

4、//从后向前比较{r[j+1]=r[j];//插入位置在前，数据向后挪j--;}r[j+1]=r[0];//插入1次移动}}7算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)稳定性：稳定82.折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(613303942

5、7085)20…...i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20lhi=820(613203039427085)9算法描述算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)算法稳定voidbinsort(intr[],intn){inti,high,x,low,m,k;for(i=2;i<=n;i++)//从第二个结点开始{r[0]=r[i];x=r[i];low=1;high=i-1;while(low<=

6、high)//二分搜索{m=(low+high)/2;if(x=low;k--)//插入位置后面结点后移r[k+1]=r[k];r[low]=r[0];//插入结点}}103.希尔排序(缩小增量分组排序法)排序过程：先取一个正整数d1

7、955657697例初始：4938659776132748554一趟排序：1327485544938659776二趟排序：1344838274955659776取d1=5一趟分组：4938659776132748554取d2=3二趟分组：132748554493865977612算法描述voidshellsort(intr[],intn,intd[T]){inti,j,k;intx;k=0;while(k