课件-8.1内排序问题基本概念

8内排序(8.1-•排序问题的基本概•排序（S排序•选择排序（堆排序•交换排–8.4.1冒泡排–8.4.2快速排•归并排•分配排序和索引排•排序算法的时间代内排序（8.1- 馆员书 、上奖学大考试成榜排列图输入法排内排序（8.1- 排序:指的是待排序记录存放在计算机随机 外部排序指的是待排序记录的数量很大，以致内存一的排序过程内排序（8.1- 小规模的排序问题-内排一个元已经有序两个元一次比若逆序一次交3次移动（赋值n个元素内排序（8.1- 8.1记录结点，进行排序的基本单关键码唯一确定记录的一个或多个排序码(Sort作为排序运算依据的一个或多个–由记录组内排序（8.1- 给定一个序列Rr1r2–其排序码分别为kk1k2排序的目的：将记录按排序–形成新的有序序列R'–相应排序码为排序码的顺–其中k'1≤k'2≤…≤k'n，称为不减–或k'1≥k'2≥…≥k'n，称为不增内排序（8.1- 正序vs.“正序”序列待排序序列正好符合排序要“逆序”序列逆序正序–逆序正序––内排序（8.1- 稳定

存在多个具有相同排序码的记排序后这些记录的相对次序保持不稳定性例– 96稳定–内排序（8.1- 稳定

存在多个具有相同排序码的记排序后这些记录的相对次序保持不稳定性例

不稳––––稳定–形式化证不稳定，反例说––内排序（8.1- 时间代记录的比较和移动次空间代算法本身的繁杂内排序（8.1- 对记录的排序码进行比较和记录的移动过最小时间代最大时间代平均时间代

内排序（8.1-

•排序问题的基本概•排序（S排序•选择排序（堆排序•交换排–8.4.1冒泡排–8.4.2快速排•归并排•分配排序和索引排•排序算法的时间代内排序（8.1- 直 排思想 利用有序表 操作进行排 :将一个记录 例，序列 内排序（8.1- 内排序（8.1- template 排序算voidInsertSort(RecordArray[],intn)//Array[]为待排序数组，n为数组长Record 临时变for(inti=1;i<n;i++) //依 第i个记TempRecord=intj=i-1;//将那些大于等于记录i的记录后while((j>=0) (TempRecord<Array[j]))Array[j+1]= j=j-}//此时j后面就是记录i的正确位置Array[j+1]=}}内排序（8.1- 稳空间代价时间代价情况：比较次数

ii

n(n1)/

(n2移动次数

i

(n2平均情况

内排序（8.1- 8.2.2 直 排序的两个性质对于短序列，直 排序比较有 内排序（8.1- 列内进行排序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接排序，内排序（8.1- 内排序（8.1- 排template<classvoid Sort(RecordArray[],intn) 排序，Array[]为待排序数组，n为数组长inti,//增量delta每次除以2递for(delta=n/2;delta>0;delta/=for(i=0;i<delta;//分别对delta个子序列进 排//“&”传Array[i]的地址，数组总长度为n-ModInsSort(&Array[i],n-i,如果增量序列不能保证最后一个delta间距为可以安排下面这个扫尾性质的排ModInsSort(Array,n,}内排序（8.1- 针对增量而修改 template<classvoidModInsSort(RecordArray[],intn,intdelta)//修改 排序算法，参数delta表示当前的增inti,for(i=delta;i<n;i+=//对子序列中第i个记录，寻找合适 位for(j=i;j>=delta;j-=delta)j以dealta为步长向前寻找逆置对进行调if(Array[jArray[j- 置swap(Arrayjj- else}}内排序（8.1- 不稳空间代价增量每次除以2递减，时间代价内排序（8.1- 增量每次除以2递减”时，效率仍然为问题：选取的增量之间并不互内排序（8.1- Hibbard增量序–{2k-1，2k-1- –如knuth的方法n/3-内排序（8.1- 8.38.3.1直接选择排直接与数组中第i个记录交换，比冒泡排序8.3.2堆排堆排序：基于最大值堆来实内排序（8.1- 内排序（8.1- template<classvoidSelectSort(RecordArray[],intn)//依次选出第i小的记录，即剩余记录中最小的那for(inti=0;i<n-1;i++)//首先假设记录i就是最小intSmallest=//开始向后扫描所有剩余记for(intj=i+1;j<n;//如果发现更小的记录，记录它的位if(Array[j]<Smallest=//将第i小的记录放在数组中第i个位swap(Array,i,}}内排序（8.1- 不稳定(见上面的例子空间代价时间代比较次数：Θ(n2)，与冒泡排序一交换次数：n-内排序（8.1- 8.3.2选择类内排直接选择排序直接从剩余记录中线性查找最大记堆排序基于最大值堆来实现，效率更选择类外排置换选择排赢者树、败方内排序（8.1- 内排序（8.1- 内排序（8.1- 内排序（8.1- 内排序（8.1- template<classvoidsort(RecordArray[],intn)intMaxHeap<Record>max_heap=MaxHeap<Record>(Array,n,n堆//算法操作n-1次，最小元素不需要出for(i=0;i<n-1;//依次找出剩余记录中的最大记录，即堆max_heap.}内排序（8.1- 例，序列 按顺序依次构造成完全二叉树的结点把完全二从下向上，父子交换7取得最小值7删除13取得次小值删除27，重新改造成新堆取得次次小值内排序（8.1- 建堆删除堆顶重新建:Θ(log一次建堆，n次删除总时间代价为Θ(nlog空间代价为内排序（8.1- 二分 算法思想 内排序（8.1- 二分 由于直 排序算法利用了有序表 操作 234设已形成有序表{ } 234设已形成有序表{ }

内排序（8.1- 二分 void emTypeR[],int{for(inti=1;i<ni++)//共进行n-1 intleft=0,right=i-1;Ele