document.write('根据定义，如果数组是一个已经排序好的数组，那么直接通过索引即可获取到所需的中位数。如果题目允许排序的话，那么本题的关键
在于选取一个合适的排序算法对数组进行排序。一般而言，快速排序的平均时间复杂度较低，为O(NlOg2N)，所以，如果采用排序方法
的话，算法的平均时间复杂度为O(Nlog2
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)。
');