# 置换选择排序

1. 取无序集合的前n个纪录，n的大小右内存工作区的最大容量决定
2. 取n个纪录中的最小值，写入一个新归并集合中
3. 此时工作取中还剩n-1个元素，取无序集合的下一个元素补齐工作区的元素为n个
4. 从n个纪录中选出比该归并段中最大值大的元素集合中的最小值，写入该归并集合，取无序集合的下一位补充工作取
5. 重复3，4直到n个纪录中找不出满足4条件的纪录
6. 重复2-6，直到所有的无序集合纪录都进入归并集合
7. 此时归并集合已经创建完成，再按照胜者树/败者树的算法排序即可

inputArr = [199383, 10, 34, -1, -32, -29, 4,
            0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
print("未排序集合:{0}".format(inputArr))
'''
构建多路集合数据
0: -1 10 34 199383
1: -32 -29 0 4 4 5 8 34 36 123 453 10080
2: 1
'''
length = len(inputArr)
sortArr = [None]*length
groupArr = []
# 工作区大小
count = 4
startIndex = count
groupIndex = 0
# length+count是为了将工作的区的数据也作为无序数组的部分，就想是一个循环数组
# 这样当startIndex>length时也不同单独处理工作区的排序，支持在压缩工作区的大小，直到工作取长度为1时结束排序
while startIndex < length+count:
    if(len(groupArr) == groupIndex):
        groupArr.append([])
    itemArr = groupArr[groupIndex]
    itemLength=len(itemArr)
    # 当startIndex>length时把数组看作循环数组，
    # 所以下一个索引就是startIndex%，
    # 但这就等于压缩了工作空间n的大小，所以工作空间的起始位置就不在为0
    firsrIndex= startIndex%length if(startIndex>length) else 0
    minIndex = firsrIndex
    minmaxIndex=None
    for index in range(firsrIndex, count):
        min = inputArr[minIndex]
        item = inputArr[index]
        # 当索引大于length时item存在None
        if(item==None):
            continue
        if(itemLength==0 and item <= min):
            minIndex = index
        if(itemLength>0 and item>=itemArr[-1]):
            if(minmaxIndex==None):
                minmaxIndex=index
                continue
            minmax=inputArr[minmaxIndex]
            if(item<minmax):
                minmaxIndex = index
    # 如果长度为0则为一个新归并段，设置第一个元素为工作区最小值
    if(len(itemArr) == 0):
        itemArr.append(inputArr[minIndex])
        inputArr[minIndex] = inputArr[startIndex%length]
    elif (minmaxIndex!=None and inputArr[minmaxIndex] >= itemArr[-1]):
        itemArr.append(inputArr[minmaxIndex])
        inputArr[minmaxIndex] = inputArr[startIndex%length]
    else:
        groupIndex += 1
        continue
    inputArr[startIndex%length]=None
    startIndex += 1

sortIndex = 0
while sortIndex < length:
    minGroupIndex = 0
    for groupIndex in range(1, len(groupArr)):
        minItem = groupArr[minGroupIndex][0]
        item = groupArr[groupIndex][0]
        minGroupIndex = minGroupIndex if(minItem < item) else groupIndex
    sortArr[sortIndex] = groupArr[minGroupIndex][0]
    del groupArr[minGroupIndex][0]
    if(len(groupArr[minGroupIndex])==0):
        groupArr.remove(groupArr[minGroupIndex])
    sortIndex += 1
print("已排序集合:{0}".format(sortArr))