期望为线性时间的选择算法（中位数算法）

问题：找出数组中第i小的元素。

思想

采用“排序+索引”的方法，其时间复杂度依赖排序算法，为O(nlogn)，并非最有效的算法。

采用类似快速排序的算法思想来进行选择，可将时间复杂度在问题平均分布的情况下降为线性的O(n)。

不同于快排的是，在定位到中位并进一步递归查找时，不需要左右两边都递归调用，仅一边递归调用即可。

代码实现

#################################
#
# Linear Time Select Algorithm
#
#################################

def linear_select(array, k, start=0, end=None):
    """
    The algorithm is similar to the Quick Sort algorithm.
    :param array: list
    :param k: int
    :param start: int
    :param end: int
    :return: the finded item
    """
    if end is None:
        end = len(array) - 1

    if start >= end:
        return array[start] 

    mid = array[start]
    i = start
    j = end
    
    while i < j:
        # From right to left
        while i < j:
            if array[j] <= mid:
                array[i] = array[j]
                i += 1
                break
            else:
                j -= 1

        # From left to right
        while i < j:
            if array[i] > mid:
                array[j] = array[i]
                j -= 1
                break
            else:
                i += 1
    array[i] = mid

    # i=j= mid pos
    print(f'li={array}, start={start}, end={end}, k={k}, mid={mid}, i={i}, j={j}')
    k_index = start + k - 1
    if i == k_index:
        return mid
    elif i < k_index:
        return linear_select(array, k_index-i, i+1, end)
    else:
        return linear_select(array, k, start, i-1)


if __name__ == "__main__":
    li = [5, 13, 2, 25, 7, 17, 20, 8, 4]
    print(li)
    selection = linear_select(li, 7)
    print(f'6th item is {selection}')