其主要思想是每趟排序在当前待排序序列中选出关键码.ppt

《其主要思想是每趟排序在当前待排序序列中选出关键码.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。有序序列r1r2ri-1rirnrk…………无序序列rnri+1r1r2ri-1……riri……交换最小记录9.3选择排序简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束例初始：[49386597761327]kjjjjjjkki=11349一趟：1

2、3[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：13273849657697voidselectSort(intr[],intn){for(i=1;ir[index];

3、}}简单选择排序算法选择排序简单选择排序算法的性能分析移动次数：最好情况（正序）：0次选择排序12345123451234512345123451234最坏情况：3(n-1)次简单选择排序算法的性能分析移动次数：最好情况（正序）：0次选择排序空间性能：需一个辅助空间。稳定性：是一种稳定的排序算法。45231152341253412354123451234比较次数：)()1(21211nOnninni=-=-å-=）（简单选择排序的时间复杂度为O(n2)。堆排序改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是

4、在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。选择排序减少关键码间的比较次数查找最小值的同时，找出较小值堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。选择排序182032364525385040281.小根堆的根结点是所有结点的最小者。2.较小结点靠近根结点，但不绝对。堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆

5、），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。选择排序503845402836322018281.大根堆的根结点是所有结点的最大者。2.较大结点靠近根结点，但不绝对。堆和序列的关系选择排序将堆用顺序存储结构来存储，则堆对应一组序列。503845402836322018285038453236402820182812345678910采用顺序存储基本思想：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一

6、个记录。选择排序堆排序需解决的关键问题?⑴如何由一个无序序列建成一个堆（即初始建堆）？⑵如何处理堆顶记录？⑶如何调整剩余记录，成为一个新堆（即重建堆）？堆调整堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？选择排序283623161825231618253628voidheapadjust(heaptype&H,ints,intm){//要筛选结点的编号为s，堆中最后一个结点的编号为mrc=H.r[s];//将筛选记录暂存for(j=2*s;j<=m;j*=2)//筛选还没有进行到叶子

7、{if(j=H.r[j])break;else{H.r[i]=H.r[j];s=j;}}H.r[i]=rc;//将筛选记录移到正确位置}选择排序堆调整——算法描述：选择排序关键问题⑴：如何由一个无序序列建成一个堆？282516231836162316282518362523162818362528233628161825算法描述：for(i=n/2;i>=1;i--)heapadjust(H,i,n);选择排序关键问题⑴：如何由一个无序序列建成

8、一个堆？最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。选择排序关键问题⑵：如何处理堆顶记录？233628161825362823251816123456对应交换162823251836123456