# 树形选择排序（锦标赛排序）

将无序集合进行两两分组排序，将找出的每组的最小值再进行两两排序，
以此模式直到找出最小的值，将这个值纪录下来并从第一次两两分组的排序集合中移除这个值，
然后进行第二轮，直到排序结束。

原始集合：{5,2,4,6,8,1,9,7,10,3}
第一次两两分组：{5,2} {4,6} {8,1} {9,7} {10,3}
第一轮：{5,2} {4,6} {8,1} {9,7} {10,3} => {2,4,1,7,3} => {2,4} {1,7} {3} => {2,1,3} => {2,1} {3} => {1,3} => {1}
第二轮：{5,2} {4,6} {8} {9,7} {10,3} => {2,4,8,7,3} => {2,4} {8,7} {3} => {2,7,3} => {2,7} {3} => {2,3} =>{2}
第三轮：{5} {4,6} {8} {9,7} {10,3} => {5,4,8,7,3} => {5,4} {8,7} {3} =>{4,7,3} => {4,7} {3} =>{4,3}=>{3}

inputArr = [199383, 10, 34, -1,-32,-29, 4, 0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
length=len(inputArr)
print("未排序集合:{0}".format(inputArr))
sortArr=[None]*len(inputArr)
for sortIndex in range(0,length):
    queryMinArr=[list(range(0,length))]
    while(len(queryMinArr)>0):
        itemArr=queryMinArr.pop()
        itemLength=len(itemArr)
        # 当itemLenth==1时表示一次排序结束，记录并在源数组中将值这是为None
        if(itemLength==1):
            sortArr[sortIndex]=inputArr[itemArr[0]]
            inputArr[itemArr[0]]=None
            break
        # 两两分组
        groupArr=[]
        itemGroupLength=itemLength//2 if(itemLength%2==0) else itemLength//2+1
        for index in range(0,itemGroupLength):
            tmpArr=[]
            # 分组时移除值为None
            for tmpIndex in range(index*2,index*2+2):
                if(tmpIndex>=itemLength):
                    continue
                if(inputArr[itemArr[tmpIndex]]!=None):
                    tmpArr.append(itemArr[tmpIndex])
            if(len(tmpArr)>0):
                groupArr.append(tmpArr)

        minItemArr=[]
        for item in groupArr :
            if(len(item)==1):
                minItemArr.append(item[0])
                continue
            minIndex =(item[0] if(inputArr[item[0]]<inputArr[item[1]]) else item[1])
            minItemArr.append(minIndex)
        queryMinArr.append(minItemArr)

print("已排序集合:{0}".format(sortArr))