填空题
冒泡排序
发布于 2022-03-03 16:13:59
牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。
在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少? 输入描述： 输入包括两行,第一行包括两个正整数n和k(2 &le n &le 50, 1 &le k &le 50),表示数组的长度和允许最多的特定操作次数。 第二行n个正整数A[i](1 &le A[i] &le 1000),表示数组内的元素,以空格分割。输入样例： 3 2 2 3 1 输出描述： 输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。输出样例 1
BubbleSort(a):
Repeat length(a)-1 times:
For every i from 0 to length(a) - 2:
If a[i] > a[i+1] then:
Swap a[i] and a[i+1]
牛牛现在要使用上述算法对一个数组A排序。在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少? 输入描述： 输入包括两行,第一行包括两个正整数n和k(2 &le n &le 50, 1 &le k &le 50),表示数组的长度和允许最多的特定操作次数。 第二行n个正整数A[i](1 &le A[i] &le 1000),表示数组内的元素,以空格分割。输入样例： 3 2 2 3 1 输出描述： 输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。输出样例 1
关注者
0
被浏览
67
