中位数以无序方式对列表进行排序

Question

根据列表中值位置的中位数以无序方式对 python 列表进行排序的最佳方法是什么？

假设：

a = [1, 3 ,6, 7, 10, 12, 17]

我在找这个：

a = [1, 17, 7, 3, 12, 6, 10]

也就是说，列表现在看起来像 [start, end, mid, first_half_mid, second_half_mid, ...]

编辑：为了进一步澄清，我正在寻找一种方法来继续平分列表，直到它覆盖整个范围！

edit2: 另一个例子来说明问题

输入：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

期望的输出：

[1, 10, 6, 3, 9, 2, 5, 8, 4, 7]

Answer 1

这看起来像是一个广度优先的任务，所以我使用了一个队列：

# from queue import Queue, Empty # python 3
from Queue import Queue, Empty   # python 2

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
accu = []
q = Queue()
# a.sort()     # if it isn't already sorted.

def do_it(l):  # whatever a precise name might be...

    global accu
    accu = [l[0], l[-1]]
    q.put(l[1:-1])             # Add first and last element, start with rest of list.
    try:
        while True:

            l = q.get_nowait()

            if not l:
                continue

            print("working on {}".format(l))
            middle = l[len(l)//2]
            left = l[:len(l)//2]
            right = l[len(l)//2+1:]

            accu.append(middle)
            q.put(left)
            q.put(right)

            print("added {}, todo: {} // {}".format(middle, left, right))
    except Empty:
        pass



print(a)
do_it(a)
print(accu)

结果：

[1, 10, 6, 4, 8, 3, 5, 7, 9, 2]

我不太明白为什么在你的评论中 10 在 6 之前。

Answer 2

更新：如果列表的长度为偶数，则将左侧元素视为中间元素

def f(a):
    # take left middle element for even-length lists
    mid = len(a)//2 if len(a)%2 else len(a)//2-1
    # take len(a)//2 as a middle element 
    #mid = len(a)//2 
    if len(a) <= 2:
        return a
    elif(len(a) == 3):
        return a[[0,-1,mid]]
    else:
        return np.append(a[[0,-1,mid]], f(np.delete(a, [0,len(a)-1,mid])))

输出：

In [153]: f(a)
Out[153]: array([ 1, 17,  7,  3, 12,  6, 10])

旧答案：

这是许多可能的解决方案之一：

import numpy as np

def f(a):
    if len(a) <= 2:
        return a
    elif(len(a) == 3):
        return a[[0,-1,len(a)//2]]
    else:
        return np.append(a[[0,-1,len(a)//2]], f(np.delete(a, [0,len(a)-1,len(a)//2])))

a = np.array([1, 3 ,6, 7, 10, 12, 17])

In [114]: a
Out[114]: array([ 1,  3,  6,  7, 10, 12, 17])

In [115]: f(a)
Out[115]: array([ 1, 17,  7,  3, 12, 10,  6])

PS 关于结果中的最后两个数字 list/array - 问题是 4 元素列表的中间索引是什么？

[3,6,10,12] 列表的中间元素是什么？在我的解决方案中，它将是 10（索引：4//2 == 2）

中位数以无序方式对列表进行排序

Median sort a list in unordered fashion

python

sorting

median

bisection