在合并排序算法中，基础子问题可以是1个元素的数组，也可以是10个元素的数组。前者不需要排序，后者可以用冒泡排序。

如果在合并排序算法的分割步骤中,将数组a[0:n-1]划分为[ ]个子数组,每个子数组中有O()个元素,然后递归地对分割后的子数组进行排序,最后将所得到的[ ]个排好序的子数组合并成所要求的排好序的数组a[0;n-1].设计一个实现上述策略的合并排序算法,并分析算法的计算复杂性.

快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。

A.分治

B.动态规划

C.贪心

D.回溯

下面程序用“冒泡”法将数组a中的10个整数按升序排列，算法是：从数组的第1个元素开始，依次将相邻的两个数相比较(第1个数与第2个数，第2个数与第3个数……如此重复)，若前面的数较大，则这两个数交换位置。这样执行一遍后，最后一个数已经是数组中最大的数。然后将数组的前n-1个数重复上述过程。如此继续，可将数组排序，请将程序补充完整。

Option Base 1

Private Sub Command1_Click()

Dim a()

a=Array(678，45，324，528，439，387，87，875，273，823)

Fori＝【 】

Forj= 【 】

If a(j)【 】a(j+1)Then

a1=a(j)

a(j)＝a(j+1)

a(j+1)=al

End lf

Nextj

Next i

For i＝1 To 10

Print a(i)

Next i

End Sub

阅读以下算法说明，根据要求回答问题1～问题3。

[说明]

快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。

1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。

2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。

3．合并：快速排序在原地排序，故无需合并操作。

下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。

A：待排序数组

p,r：数组元素下标，从p到r

q：划分的位置

x：枢轴元素

i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值

j：循环控制变量，表示数组元素下标

●对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+l到nl+n2个元素赋值为0，最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为(64)。

针对二分查找算法，假设一个有序数组有136个元素，那么要查找到第10个元素，需要比较的元素为()

A.68,34,17,9,13,11,10

B.68,34,17,8,12,10

C.69,35,18,10

D.68,34,18,9,13,11,10

以下是一个对数组A(含有n个数值元素)进行排序的算法伪代码，请问它的平均时间复杂度是多少()

A.O(n)

B.O(n^2)

C.O(1)

D.O(log(n))

有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1)(3分)给出适用于计数排序的数据表定义； (2)(7分)使用Pascal或C语言编写实现计数排序的算法； (3)