锦标赛排序

前言

这种排序方式的经典应用来自百度的一道面试题：给出一个长度是N的数组，现在要找出最小的两个元素，最少要多少次比较？

原理

竞标赛排序又叫树型排序，属于选择排序的一种，其目的是克服直接选择排序不能保留比较结果，不断重复比较的缺点，它的基本思想是首先取得n个元素的关键词，进行两两比较，得到n/2个比较优胜者，然后再两两比较找到第一小的那个，然后把最小那个元素对应的叶子节点的值变为无穷大，那么在搜索第二小值时，我们就只需要比较最小值叶子节点所在的子树即可，就达到了logn次比较的目标，然后一直重复该过程，所以其时间复杂度为O(n*log2n),空间复杂度为O（N）(需要2n-1个节点存放树) 示意图 ## 代码实现（python）

class Node:
    def __init__(self, _data, _id):
        self.data = _data
        self.id = _id
    def show(self):
        print(self.id, self.data)


def Adjust(data, idx):
    while (idx != 0):
        if (idx % 2 == 1):
            if (data[idx].data < data[idx + 1].data):
                data[(idx - 1) // 2] = data[idx]
            else:
                data[(idx - 1) // 2] = data[idx + 1]
            idx = (idx - 1) // 2
        else:
            if (data[idx - 1].data < data[idx].data):
                data[idx // 2 - 1] = data[idx - 1]
            else:
                data[idx // 2 - 1] = data[idx]
            idx = idx // 2 - 1
    return data


def Sort(data):
    length = len(data)
    n = 1
    while n < length:
        n <<= 1
        # print("n=",n)
    nTreeSize = 2 * n - 1
    nodes = []
    for i in range(nTreeSize):
        nodes.append(Node(0, 0))
    # 初始化竞赛数数据
    for i in range(n - 1, nTreeSize):
        idx = i - (n - 1)
        if idx < length:
            nodes[i] = Node(data[idx], i)
        else:
            nodes[i] = Node(9999, -1)
    for i in range(n - 2, -1, -1):
        if (nodes[i * 2 + 1].data < nodes[i * 2 + 2].data):
            nodes[i] = nodes[i * 2 + 1]
        else:
            nodes[i] = nodes[i * 2 + 2]
    # 实现排序
    B = []
    for i in range(0, length):
        # 取出最小的
        B.append(nodes[0].data)
        nodes[nodes[0].id].data = 9999
        Adjust(nodes, nodes[0].id)
    return B


if __name__ == "__main__":
    Arr = [2,5,9,1,11,20,15,7,4,6]
    Arr2 = Sort(Arr)
    print("newArr=",Arr2)

## 参考资料 james1207 mmmmmmmmzw