数据结构作业
第三次：第一题
第三次：第二题
第三次：第二题："matrix.txt"
第三次：第三题
第三次：第三题：“matrix2.txt”
第四次：题目说明
数据结构第七章章节测试
第四次：第一题
第四次：第二题：shell_sort
第四次：第二题：quick_sort
第四次：第二题：merge_sort
本文档使用 MrDoc 发布
-
+
home page
第四次：题目说明
1. 寻找大富翁： 假设给出N个人的个人资产值，请使用堆排序快速找出资产排前M位的大富翁。 2. 给定数组 `{48,27,96,48,25,6,90,17,84,62,49,72,17}` 请分别使用**希尔排序**、**快速排序**和**归并排序**分别进行排序，输出排序过程中每一趟操作结果，分析比较交换和比较次数以及排序结果是否稳定。 > - 稳定性的定义: 数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。 > - 稳定性的意义: 如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。 > - 希尔排序： 希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。 > - 归并排序： 归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。 > - 快速排序： 快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素， 然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。 3. 试设计一个算法: 已知`{x0,x1,x2,……,xn-1}`是一个堆，要求删除其中一个记录结点`x[i]`后，还是堆。 提示：先将`x[i]`保存，将堆中最后一个元素换至`x[i]`，并将堆长度减 1；再从位置 i 开始向下调整，使其满足堆性质。
cdcdcd
Dec. 9, 2022, 12:53 a.m.
转发文档
Collection documents
Last
Next
手机扫码
Copy link
手机扫一扫转发分享
Copy link
Markdown文件
PDF文档（打印）
share
link
type
password
Update password
