【正确答案】根据定义，如果数组是一个已经排序好的数组，那么直接通过索引即可获取到所需的中位数。如果题目允许排序的话，那么本题的关键在于选取一个合适的排序算法对数组进行排序。一般而言，快速排序的平均时间复杂度较低，为O(NlOg2N)，所以，如果采用排序方法的话，算法的平均时间复杂度为O(Nlog₂^N)。
   可是，题目要求，不许使用排序算法。那么前一种方法显然走不通。此时，可以换一种思路：分治的思想。快速排序算法在每一次局部递归后都保证某个元素左侧的元素的值都比它小，右侧的元素的值都比它大，因此，可以利用这个思路快速地找到第N大元素，而与快速排序算法不同的是，这种方法关注的并不是元素的左右两边，而仅仅是某一边。
   根据快速排序的方法，可以采用一种类似快速排序的方法，找出这个中位数。具体而言，首先把问题转化为求一列数中第i小的数的问题，求中位数就是求一列数的第(length/2+1)小的数的问题(其中length表示的是数组序列的长度)。
   当使用一次类快速排序算法后，分割元素的下标为pos：
   (1)当pos＞length/2时，说明中位数在数组左半部分，那么继续在左半部分查找。
   (2)当pos=lengh/2时，说明找到该中位数，返回A[pos]即可。
   (3)当pos＜length/2时，说明中位数在数组右半部分，那么继续在数组右半部分查找。
   以上默认此数组序列长度为奇数，如果为偶数就是调用上述方法两次找到中间的两个数求平均值。示例代码如下：
   class Test:
   def __new__(self):
   self.pos=0
   #以arr[low]为基准把数组分成两部分
   def partition (self,arr,low,high):
   key=arr[low]
   while low＜high:
   while low＜high and arr[high]＞key:
   high-=1
   arr[low]=arr[high]
   while low＜high and arr[low]＜key:
   low+=1
   arr[high]=arr[low]
   arr[low]=key
   self.pos=low
   
   def getMid(self,arr):
   low=0
   n=len(arr)
   high=n-1
   mid=(low+high)/2
   while True:
   #以arr[low]为基准把数组分成两部分
   self.partition(arr,low,high)
   if self.pos==mid:# 找到中位数
   break
   elif self.pos＞mid: # 继续在右半部分查找
   high=self.pos-1
   else: #继续在左半部分查找
   low-self.pos+1
   #如果数组长度是奇数, 中位数为中间的元素, 否则就是中间两个数的平均值
   return arr[mid] if (n%2)!=0 else (arr[mid]+arr[mid+1])/2
   
   if __name__="__main__":
   arr=[7,5,3,1,11,9]
   print Test().getMid(arr)
   程序的运行结果为：
   6
   算法性能分析：
   这种方法在平均情况下的时间复杂度为O(N)。

【答案解析】[考点] 如何在不排序的情况下求数组中的中位数