# 置换选择排序
置换选择排序是对多路平衡归并排序算法的优化，主要优化的是生成多路归并集合的过程。
# 原理
代码语言：javascript复制1. 取无序集合的前n个纪录，n的大小右内存工作区的最大容量决定
2. 取n个纪录中的最小值，写入一个新归并集合中
3. 此时工作取中还剩n-1个元素，取无序集合的下一个元素补齐工作区的元素为n个
4. 从n个纪录中选出比该归并段中最大值大的元素集合中的最小值，写入该归并集合，取无序集合的下一位补充工作取
5. 重复3，4直到n个纪录中找不出满足4条件的纪录
6. 重复2-6，直到所有的无序集合纪录都进入归并集合
7. 此时归并集合已经创建完成，再按照胜者树/败者树的算法排序即可# 实现
代码语言：javascript复制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))
