你可能喜欢
问答题
问答题
有一种简单的排序算法,叫做计数排序(count Sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录,统计出的计数值为 c,那么,这个记录在新的有序表中的合适的存放位置即为 c。
(1)给出适用于计数排序的数据表定义;
(2)使用C++语言编写实现计数排序的算法。
问答题
下面的程序是一个的两路归并算法merge,只需要一个附加存储。设算法中参加归并的两个归并段是A[left]~A[mid]和A[mid]~A[right],归并后结果归并段放在原地。
若A = { 12, 28, 35, 42, 67, 9, 31, 70 }, left = 0, mid = 4, right = 7。写出每次执行算法最外层循环后数组的变化,并给出每次执行算法最外层循环时的数据记录移动次数。