|
以关键字序列()为例分别写出执行以下排序算法的各趟排序结束时关键字序列的状态 () 直接插入排序 ()希尔排序 ()冒泡排序 ()快速排序 () 直接选择排序 () 堆排序 () 归并排序 ()基数排序 上述方法中哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例 答 ()直接插入排序:(方括号表示无序区) 初始态: [ ] 第一趟 [ ] 第二趟 [ ] 第三趟 [ ] 第四趟 [ ] 第五趟 [ ] 第六趟 [ ] 第七趟 [ ] 第八趟 [] 第九趟 ()希尔排序(增量为) 初始态: 第一趟 第二趟 第三趟 ()冒泡排序(方括号为无序区) 初始态 [ ] 第一趟 [ ] 第二趟 [ ] 第三趟 [ ] 第四趟 [ ] 第五趟 [ ] 第六趟 ()快速排序（方括号表示无序区层表示对应的递归树的层数） 初始态 [ ] 第二层 [ ] [ ] 第三层 [] [ ] [ ] 第四层 [] [ ] [] 第五层 [] 第六层 ()直接选择排序(方括号为无序区) 初始态 [ ] 第一趟 [ ] 第二趟 [ ] 第三趟 [ ] 第四趟 [ ] 第五趟 [ ] 第六趟 [ ] 第七趟 [ ] 第八趟 [ ] 第九趟 ()堆排序（通过画二叉树可以一步步得出排序结果） 初始态 [ ] 建立初始堆 [ ] 第一次排序重建堆[ ] 第二次排序重建堆[ ] 第三次排序重建堆[ ] 第四次排序重建堆[ ] 第五次排序重建堆[ ] 第六次排序重建堆[ ] 第七次排序重建堆[ ] 第八次排序重建堆[ ] 第九次排序重建堆 ()归并排序（为了表示方便采用自底向上的归并方括号为有序区） 初始态[] [] [] [] [] [] [] [] [] [] 第一趟[ ] [ ] [ ] [ ] [ ] 第二趟[ ] [ ] [ ] 第三趟[ ] [ ] 第四趟[ ] ()基数排序（方括号内表示一个箱子共有个箱子箱号从到） 初始态 第一趟[] [ ] [] [] [] [] [] [] [] [] 第二趟[] [] [] [ ] [] [] [ ] [] [] [] 第三趟[] [] [] [] [] [] [] [ ] [] [] 在上面的排序方法中直接插入排序冒泡排序归并排序和基数排序是稳定的其他排序算法均是不稳定的现举实例如下以带*号的表示区别 希尔排序[*] 快速排序[*] 直接选择排序[*] 堆排序[*] 上题的排序方法中哪些易于在链表(包括各种单双循环链表)上实现? 答 上题的排序方法中直接插入排序冒泡排序直接选择排序基数排序和归并排序等方法易于在链表上实现 当R[lowhigh]中的关键字均相同时Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion使得划分结果是平衡的(即划分后左右区间的长度大致相等)? 答 此时Partion 返回值是low此时快速排序的运行时间是 (highlow)(highlow)/=O((highlow)^)可以修改Partion 将其中RecType pivot=R[i];句改为RecType pivot=R[(j+i)/]也就是取中间的关键字为基准这样就能使划分的结果是平衡的 若文件初态是反序的则直接插入直接选择和冒泡排序哪一个更好? 答 应选直接选择排序为更好分析如下 ()在直接插入排序算法中反序输入时是最坏情况此时 关键字的比较次数Cmax=(n+)(n)/; 记录移动次数为Mmax=(n)(n+)/; Tmax=n^n (以上二者相加) ()在冒泡排序算法中反序也是最坏情况此时 Cmax=n(n)/; Mmax=n(n)/ Tmax=n^n ()在选择排序算法中 Cmax=n(n)/ Mmax=(n) Tmax=n^/n/ 由此可见虽然它们的时间复杂度都是O(n^)但是选择排序的常数因子为/因此选择排序最省时间 若文件初态是反序的且要求输入稳定则在直接插入直接选择冒泡和快速排序中就选选哪种方法为宜? 答 这四种排序算法中直接选择快速排序均是不稳定的因此先予以排除剩下两种算法中由于直接插入算法所费时间比冒泡法更少(见上题分析)因此选择直接排序算法为宜 有序数组是堆吗? 答 有序数组是堆因为有序数组中的关键字序列满足堆的性质若数组为降序则此堆为大根堆反之为小根堆 高度为h的堆中最多有多少个元素?最少有多少个元素?在大根堆中关键字最小的元素可能存放在堆的哪些地方? 答 高度为h的堆实际上为一棵高度为h的完全二叉树因此根据二叉树的性质可以算出它最少应有h个元素最多可有h个元素(注意一个有括号一个没有)在大根堆中关键字最小的元素可能存放在堆的任一叶子结点上 判别下列序列是否为堆(小根堆或大根堆)若不是则将其调整为堆 () (); () (); () (); () () 答 堆的性质是任一非叶结点上的关键字均不大于(或不小于)其孩子结点上的关键字据此我们可以通过画二叉树来进行判断和调整 () 此序列是大根堆
|
