题目要求

最近做了一道题，题目是这样的：

找到一个巨大数组的中位数。
# demo：[1,100,2,5,12,44,88,77,54,932,61]

解题方法

巨大的数组，排序肯定不是最优解了，解题思路可以借鉴快排算法那种分而治之的思想。

详情直接看代码实现吧。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: toddler

import random
import statistics
import time
import sys
sys.setrecursionlimit(1000000)


def find_mid(mid_index, __list):
    """
    寻找中位数算法
    :param mid_index: 中位数索引
    :param __list: 目标数组
    :return: 中位数数值
    """
    # 随机取一个数作为分割元素, 以分割元素为界限，将数组分割大小两部分
    random_num = random.choice(__list)
    small_list = [i for i in __list if i < random_num]
    # 若小数组的右端索引大于中位数索引, 则继续缩小小数组的区间长度, 这样可以直接舍弃比中位数大的元素, 减少计算量
    if len(small_list) > mid_index:
        return find_mid(mid_index, small_list)
    # 分割点左边的元素没有价值, 被舍弃, 相应的中位数索引左移对应长度, 保证相对原始数据索引长度不变
    mid_index -= len(small_list)
    # 判断分割点有几个, 若分割点所占空间长度大于新的中位数索引, 则分割点就是中位数
    same_mid_num = __list.count(random_num)
    if same_mid_num > mid_index:
        return random_num
    # 接下来向右计算, 所以切分点所占据的索引区间元素将不在计算, 大数组将舍弃这些值, 因此调整中位数的索引值
    mid_index -= same_mid_num
    big_list = [i for i in __list if i > random_num]
    return find_mid(mid_index, big_list)


def run(__list):
    """
    调度处理算法无关的业务逻辑
    :param __list: 目标数组
    :return: 中位数数值
    """
    list_length = len(__list)
    if list_length != 0:
        # 判断奇数个还是偶数个
        if list_length % 2:
            mid_index = list_length // 2
            print("奇数个数字: {}".format(list_length))
            return find_mid(mid_index, __list)
        else:
            print("偶数个数字: {}".format(list_length))
            left_num = find_mid((list_length - 1) // 2, __list)
            right_num = find_mid((list_length + 1) // 2, __list)
            return (left_num + right_num) / 2
    else:
        return "输入列表是否为空"


def test(test_data):
    """
    测试验证
    :param test_data: 待测数组
    :return:
    """
    # print('原始数据: {}'.format(test_data))
    stand_s_time = time.clock()
    expect_mid = statistics.median(test_data)
    stand_e_time = time.clock()
    print("statistics计算耗时: {}".format(stand_e_time - stand_s_time))
    start_time = time.clock()
    actual_mid = run(test_data)
    end_time = time.clock()
    print("我的算法计算耗时: {}".format(end_time-start_time))
    print('期望结果: 中位数为{}'.format(expect_mid))
    print('实际结果: 中位数为{}'.format(actual_mid))
    assert expect_mid == actual_mid, '计算错误'


demo_list = [1, 100, 2, 5, 12, 44, 88, 77, 54, 932, 61]
print('样例测试=====>')
test(demo_list)
print('\r\n大数据量测试======>')
test([random.randint(0, int(1e6)) for _ in range(int(1e6))])

测试结果

测试环境：

硬件	参数
CPU	Intel(R) Core(TM) i3-4370 CPU @ 3.80GHz
MEM	8G DDR3

算法表现，稳定性不是很好：

数据量	排序时间
10 ^ 6	0.5 s
10 ^ 7	5 ~ 6 s
10 ^ 8	65 ~ 100 s

总结分析

最差时间分析	平均时间复杂度	稳定度	空间复杂度
O(n)	O(logn)	不稳定	O(logn)