无序数组求中位数

Question

中位数是一个有序数组中中间位置的数，所以要先将无序数组排序，然后再找出中间位置的数。

方法一：排序后取中位数

1. 将无序数组进行排序（可以使用快速排序等），得到有序数组；
2. 如果数组长度为奇数，则中位数为有序数组的中间位置的数；
3. 如果数组长度为偶数，则中位数为有序数组中间两个位置的数的平均值。

方法二：利用快速排序思想

快速排序的思想是将数组分成两个部分，并找到一个基准值（pivot），使得左半部分所有元素都小于等于基准值，右半部分所有元素都大于等于基准值。如果基准值正好在数组中间位置，则它就是中位数。

具体实现步骤如下：

1. 随机选择一个元素作为基准值；
2. 将数组中所有小于基准值的元素放在左边，大于基准值的元素放在右边，相等的元素可以放在任何一边；
3. 比较左边元素的数量和右边元素的数量，如果相等，则说明基准值正好在中间位置，直接返回基准值；
4. 如果左边元素的数量小于右边，则在右半部分继续查找中位数；
5. 如果左边元素的数量大于右边，则在左半部分继续查找中位数。

代码实现

方法一：

def find_median(nums):
    nums.sort()
    n = len(nums)
    if n % 2 == 0:
        return (nums[n//2-1] + nums[n//2]) / 2
    else:
        return nums[n//2]

方法二：

import random

def partition(nums):
    pivot = nums[0]
    i, j = 1, len(nums)-1
    while i <= j:
        while i <= j and nums[i] <= pivot:
            i += 1
        while i <= j and nums[j] >= pivot:
            j -= 1
        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]
    nums[0], nums[j] = nums[j], nums[0]
    return j

def find_median(nums):
    if len(nums) % 2 == 0:
        k1, k2 = len(nums) // 2 - 1, len(nums) // 2
        while True:
            idx = partition(nums)
            if idx == k1:
                return (nums[k1] + nums[k2]) / 2
            elif idx < k1:
                nums = nums[idx+1:]
                k1 -= idx+1
                k2 -= idx+1
            else:
                nums = nums[:idx]
    else:
        k = len(nums) // 2
        while True:
            idx = partition(nums)
            if idx == k:
                return nums[k]
            elif idx < k:
                nums = nums[idx+1:]
                k -= idx+1
            else:
                nums = nums[:idx]

测试：

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(find_median(nums))  # 4