1.设A是n个不等的数的数组，n>2。以比较作为基本运算，试给出一个0（1）时间的算法，找出A中一个既不是最大也不是最小的数。写出算法的伪码，说明该算法在最坏情况下执行的比较次数。

在数学上，任何包含三个或以上不同数的数组中，不可能存在一个既不是最大也不是最小的数，因为至少会有两个数是相同的。但是在计算机科学中，我们可以考虑算法，通过比较找出一个数组中满足条件的数，即使这在数学上不可能实现。

然而，如果我们要找出一个既不是最大也不是最小的数，我们可以假设数组中的数字是不重复的，然后使用一种快速选择算法，比如快速排序的选择过程（QuickSelect），来找到中位数，也就是在排序后位于中间位置的数，这样它既不是最大也不是最小的数。

快速选择算法的基本思想是划分数组，使得划分后的左侧所有元素都不大于右侧所有元素，然后根据目标位置来决定是继续在左侧找还是在右侧找。在最坏情况下，算法的性能是O(n^2)，但如果采用随机化策略，平均性能可以达到O(n)。

下面是寻找中位数的快速选择算法的伪码，这个版本是基于快速排序选择过程的简单实现：

function QuickSelect(A, left, right, k)
    if left = right
        return A[left]
    pivotIndex <- Partition(A, left, right)
    if k = pivotIndex
        return A[k]
    else if k < pivotIndex
        return QuickSelect(A, left, pivotIndex - 1, k)
    else
        return QuickSelect(A, pivotIndex + 1, right, k)
end function

function Partition(A, left, right)
    pivot <- A[right]
    i <- left
    for j <- left to right - 1
        if A[j] <= pivot
            swap A[i] with A[j]
            i <- i + 1
    swap A[i] with A[right]
    return i
end function

在这个算法中，`A` 是原始数组，`left` 和 `right` 是数组的左右边界索引，`k` 是目标位置。对于找中位数的问题，`k` 将会是数组长度的中间索引。

在最坏的情况下，比较次数是O(n^2)。但是在实际应用中，通过随机选择枢轴或者使用中位数的中位数作为枢轴等策略可以使得算法的平均性能接近O(n)。