目录：

1、快速排序

2、合并排序

   在排序一中介绍了三种简单的排序算法，它们的时间复杂度都是o(n^2)，本节将介绍两种更快的排序算法，它们采用的是“分而治之”（divide-and-conquer）的策略，也就是说每个算法都找到了一种方法将列表分解为更小的子列表，随后再递归地排序，时间复杂度为O（nlog(n)）。

1、快速排序

   （1）从列表的中点位置选取一项，作为基准点（pivot 选取方法有多种）；

   （2）将列表中项分区，小于基准点的项移动到基准点左边，大于基准点的项移动到右边；

   （3）分而治之，对于（2）中得到的两个子列表，递归地重复（2）的处理过程；

   （4）每次遇到少于2个项的一个子列表，则结束该过程；

   该算法最复杂的部分在于对子列表中的项进行分割的操作，基本思路为：

   （1）将基准点和子列表中的最后一项交换；

   （2）在已知小于基准点的项和剩余的项之间建立一个边界，一开始，这个边界就放在第一个项之前；

   （3）从子列表的第1项开始扫描整个子列表，每次遇到小于基准点的项，就将其与边界之后的第一项交换，并且边界向后移动；

   （4）将基准点和边界之后的第一项交换，从而完成整个过程；

#快速排序
class quicksort():

    def __init__(self,lyst):

self.quicksortHelper(lyst,0,len(lyst)-1)

#递归调用此过程
def quicksortHelper(self,lyst,left,right):

        if left<right:
pivotlocation = self.partition(lyst,left,right)
self.quicksortHelper(lyst,left,pivotlocation-1)
self.quicksortHelper(lyst,pivotlocation+1,right)

#left:子列表最左索引
    #right：子列表最优索引
def partition(self,lyst,left,right):

middle=(left + right)//2
pivot = lyst[middle]    #选定基准点

lyst[middle] = lyst[right]  #基准点与最后一项进行交换
lyst[right] = pivot

        boundary = left #设置边界
        #从第一项开始扫描整个列表
for index in range(left,right):
            if lyst[index] < pivot:         #每当遇到小于基准点的项
swap(lyst,boundary,index)   #将该项与boundary位置的项进行交换
boundary += 1               #并将边界后移
swap(lyst,boundary,right)           #最后将基准点与boundary位置的项进行交换

return boundary                     #返回当前分割点

   复杂度分析：每次分割的过程的工作量与列表长度n成正比，只需确定对列表分割的次数，当每次分割的分割线都尽可能的靠近当前子列表的中央，那么大概经过log（n）步之后会得到一个单一的元素，因此该算法最好的性能为O（nlog(n)）。对于最坏的情况是当一个列表为有序时，性能为O（n^2）.

   基准点的选择：在第一个位置和最后一个位置选择基准点不是一种明智的选择，可以选择一个随机位置，可以选择中间元素，有助于接近最优性能。

2、合并排序

   思路：

       计算一个列表的中间位置，并且递归地排序其左边和右边的子列表；

       将两个排好序的子列表重新合并为单个的排好序的列表；

       当子列表不再能够划分时，停止这个过程；

   将两个排好序的子列表合并到一个大的排好序的子列表中，步骤如下：

      （1） 将索引指针设置为每个子列表的第一项；

       （2）从每个子列表的第一项开始，重复比较各项，将较小的项从其子列表中复制到复制缓存中，并且继续处理子列表的下一项。重复这个过程，直到两个子列表中的所有项都已经复制过了。如果先到达了其中的一个子列表的末尾，通过从另一个子列表复制剩余的项，从而结束这个步骤.

       （3）将缓存中的数据复制会原列表中。

def merge(self,lyst,copyBuffer,low,middle,high):
    pass
"""
    lyst        list that is being sorted
    copyBuffer  temp space needed during the merge process
    low         begining of first sorted sublist
    middle      end of first sorted sublist
    middle+1    begining of second sorted sublist
    high        end of second sorted sublist
   """
#initialize i1 and i2 to the first items in each sublist
i1=low
i2=middle+1

#interleave items from the sublists into the copyBuffer in such a way that order is maintained
for i in range(low,high+1):
        if i1 >middle:
copyBuffer[i]=lyst[i2]      #first sublist exhausted
i2 += 1
elif i2>high:
copyBuffer[i]=lyst[i1]
            i1 += 1
elif lyst[i1]<lyst[i2]:
copyBuffer[i]=lyst[i1]
            i1 += 1
else:
copyBuffer[i]=lyst[i2]
            i2 += 1

for i in range(low,high+1):
lyst[i]=copyBuffer[i]

   再递归调用上述过程：首先计算子列表的中点，递归地对中点以下和中点以上的部分进行排序。

def mergeSortHelper(self,lyst,copyBuffer,low,high):
    pass
"""
    lyst        list being sorted
    copyBuffer  temp space needed during merge
    low,high    bounds of sublist
    middle      midpoint of sublist
   """
if low < high :
middle = (low + high)//2
self.mergeSortHelper(lyst,copyBuffer,low,middle)
self.mergeSortHelper(lyst,copyBuffer,middle+1,high)
self.merge(lyst,copyBuffer,low,middle,high)

   复杂度分析：每层合并花费时间为O（n），但由于划分时都为平均分割子列表，所以层数为O（log(n)）,

所以该函数的最大运行时间为O（nlog(n)）.

   其次根据列表的大小，合并排序有两个空间需求，首先是在支持递归调用的调用栈上需要O（logn）的空间，复制缓存需要使用O（n）的空间。