但行好事，莫问前程

0%

无序大数组的中位数算法

发表于 更新于 分类于

题目要求

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

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

解题方法

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

详情直接看代码实现吧。

1
#!/usr/bin/env python
2
# -*- coding:utf-8 -*-
3
# author: toddler
4
5
import random
6
import statistics
7
import time
8
import sys
9
sys.setrecursionlimit(1000000)
10
11
12
def find_mid(mid_index, __list):
13
    """
14
    寻找中位数算法
15
    :param mid_index: 中位数索引
16
    :param __list: 目标数组
17
    :return: 中位数数值
18
    """
19
    # 随机取一个数作为分割元素, 以分割元素为界限，将数组分割大小两部分
20
    random_num = random.choice(__list)
21
    small_list = [i for i in __list if i < random_num]
22
    # 若小数组的右端索引大于中位数索引, 则继续缩小小数组的区间长度, 这样可以直接舍弃比中位数大的元素, 减少计算量
23
    if len(small_list) > mid_index:
24
        return find_mid(mid_index, small_list)
25
    # 分割点左边的元素没有价值, 被舍弃, 相应的中位数索引左移对应长度, 保证相对原始数据索引长度不变
26
    mid_index -= len(small_list)
27
    # 判断分割点有几个, 若分割点所占空间长度大于新的中位数索引, 则分割点就是中位数
28
    same_mid_num = __list.count(random_num)
29
    if same_mid_num > mid_index:
30
        return random_num
31
    # 接下来向右计算, 所以切分点所占据的索引区间元素将不在计算, 大数组将舍弃这些值, 因此调整中位数的索引值
32
    mid_index -= same_mid_num
33
    big_list = [i for i in __list if i > random_num]
34
    return find_mid(mid_index, big_list)
35
36
37
def run(__list):
38
    """
39
    调度处理算法无关的业务逻辑
40
    :param __list: 目标数组
41
    :return: 中位数数值
42
    """
43
    list_length = len(__list)
44
    if list_length != 0:
45
        # 判断奇数个还是偶数个
46
        if list_length % 2:
47
            mid_index = list_length // 2
48
            print("奇数个数字: {}".format(list_length))
49
            return find_mid(mid_index, __list)
50
        else:
51
            print("偶数个数字: {}".format(list_length))
52
            left_num = find_mid((list_length - 1) // 2, __list)
53
            right_num = find_mid((list_length + 1) // 2, __list)
54
            return (left_num + right_num) / 2
55
    else:
56
        return "输入列表是否为空"
57
58
59
def test(test_data):
60
    """
61
    测试验证
62
    :param test_data: 待测数组
63
    :return:
64
    """
65
    # print('原始数据: {}'.format(test_data))
66
    stand_s_time = time.clock()
67
    expect_mid = statistics.median(test_data)
68
    stand_e_time = time.clock()
69
    print("statistics计算耗时: {}".format(stand_e_time - stand_s_time))
70
    start_time = time.clock()
71
    actual_mid = run(test_data)
72
    end_time = time.clock()
73
    print("我的算法计算耗时: {}".format(end_time-start_time))
74
    print('期望结果: 中位数为{}'.format(expect_mid))
75
    print('实际结果: 中位数为{}'.format(actual_mid))
76
    assert expect_mid == actual_mid, '计算错误'
77
78
79
demo_list = [1, 100, 2, 5, 12, 44, 88, 77, 54, 932, 61]
80
print('样例测试=====>')
81
test(demo_list)
82
print('\r\n大数据量测试======>')
83
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)