快速排序

原理

取无序集合中任意一个元素（通常选集合的第一个元素）作为分界点，将小的放左边，大的放右边，此时集合被划分三段，
然后将左边，右边集合分别使用之前的集合划分方式，直到最后每个集合中的元素都是1个，
最后合并集合即得到有序集合。

原始集合：{5,2,4,6,8,1,9,7,10,3}
取任意一个元素：5，分割后为{2,4,1,3} {5} {6,8,9,7,10}
分别取多个子集合的任意一个元素：
	* 第一个子集合：{1} {2} {4,3}
	* 第二个子集合：{5}
	* 第三个子集合：{6} {8,9,7,10}
按上一步的模式继续拆分集合：
	{1}
	{2}
	{3} {4}
	{5}
	{6}
	{7}{8}{9,10}
继续拆分：	
	{1}
	{2}
	{3} 
	{4}
	{5}
	{6}
	{7}
	{8}
	{9} {10}
最后发现每个集合都是1个元素，拆无可拆时排序结束。

原理图

无

实现一

通过临时数组保存分组数据

def splitSortArr1(arr):
    if(len(arr)<=1):
        return arr
    splitItem=arr[0]
    leftArr=[]
    rightArr=[]
    for item in arr[1:]:
        if(item>=splitItem):
            rightArr.append(item)
        else:
            leftArr.append(item)
    sortArr=[]
    for item in (splitSortArr1(leftArr)):
        sortArr.append(item)
    sortArr.append(splitItem)
    for item in (splitSortArr1(rightArr)):
        sortArr.append(item)
    return sortArr
inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
print("未排序集合:{0}".format(inputArr))
inputArr=splitSortArr1(inputArr)
print("已排序集合:{0}".format(inputArr))

实现二

在原数组上排序

def splitSortArr2(arr, start, end):
    if(start==end):
        return
    splitIndex = start
    splitItem = arr[splitIndex]
    for index in range(start+1, end):        
        currItem = arr[index]
        currIndex=index
        if(splitItem >= currItem):
            while(currIndex!=splitIndex):
                arr[currIndex]=arr[currIndex-1]
                currIndex-=1
            inputArr[splitIndex]=currItem
            splitIndex += 1
    splitSortArr2(arr,start,splitIndex)
    splitSortArr2(arr,splitIndex+1,end)
inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
print("未排序集合:{0}".format(inputArr))
splitSortArr2(inputArr,0,len(inputArr))
print("已排序集合:{0}".format(inputArr))

实现三 （推荐）

使用堆代替递归，防止递归太深导致栈溢出

def splitSortArr3(arr,indexs):
    start=indexs[0]
    end=indexs[1]
    if(start==end):
        return
    splitIndex = start
    splitItem = arr[splitIndex]
    for index in range(start+1, end):        
        currItem = arr[index]
        currIndex=index
        if(splitItem >= currItem):
            while(currIndex!=splitIndex):
                arr[currIndex]=arr[currIndex-1]
                currIndex-=1
            inputArr[splitIndex]=currItem
            splitIndex += 1
    queue.append([start,splitIndex])
    queue.append([splitIndex+1,end])
inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
print("未排序集合:{0}".format(inputArr))
queue=[[0,len(inputArr)]]
while len(queue)>0:
    splitSortArr3(inputArr,queue.pop(0))
print("已排序集合:{0}".format(inputArr))