本文共 2976 字，大约阅读时间需要 9 分钟。

归并排序

性能稳定

平均时间复杂度为 O(nlogn) 最好时间复杂度为 O(nlogn) 最坏时间复杂度为 O(nlogn) 核心思想： (1) 分：只要可以分，就可以将list中的元素分成两半，直到不能分则跳出 (2) 比：对于传入两个list,则要比较排序,则为了提高效率,输入为有序list, (3) 合：对于输入两个有序的list ,输出为一个有序的list. (4) 迭代：每次分比合得出的结果 都要迭代，直到全部输出

def MergerSort(list):    "list的拆分"    if len(list) <= 1 :        return list    else:        num = int(len(list)/2)        "核心：分成的两部分也要继续分下去,所以这里是"        "拆分函数的迭代，直到list的分解长度为1"        left = MergerSort(list[:num])        right = MergerSort(list[num:])        return Merge(left,right)def Merge(left,right):    "将两个list中的元素排序"    i ,j = 0, 0    result = []    while i < len(left) and j < len(right):        if left[i] >= right[j]:            result.append(right[j])            j += 1        else:            result.append(left[i])            i += 1    "核心：当跳出while循环时,说明一个list已经全部加入result"    "其余元素可以直接加入result,这个使用切片，切片是支持超出index的部分的"    "如：l= [1,2]  l[3:] = []"    result += left[i:]    result += right[j:]    return result

---

快速排序

快速排序 性能不稳定

平均时间复杂度 O(nlogn) 最好时间复杂度 O(nlogn) 最差时间复杂度 O(n2)

核心思想 ：

每一次循环会有选择一个key，从list尾处循环找比key小元素位置J,并将放置在i位置 从list头找比key大的放置在j 位置,

import numpy as npdef QuickSort(lis,low,high):    i = low    j = high    if i >= j:        return lis    # if 部分是核心部分    # 后半部分迭代的时候的跳出条件就是i>=j,否则是没法跳出的"    key = lis[i]    # 注意  key= list[i] 一定在 跳出条件后面，否则    while i < j :        while i < j and lis[j] >= key:            j -= 1        lis[i] = lis[j]        while i < j and lis[i] <= key:            i += 1        lis[j] = lis[i]    lis[i] = key    "每一次循环while都是把list分成两部分，左面是比key小的元素,右边是比key大的元素"    QuickSort(lis,low,i-1)    QuickSort(lis,j+1,high)    return lisif __name__ == '__main__':    lis = np.random.randint(1,1000,10)    lis_ = list(lis)    print lis_    low_ = 0    high_ = len(lis_) - 1    print QuickSort(lis_,low_,high_)

运行结果

[44, 514, 266, 369, 215, 398, 727, 835, 939, 378] [44, 215, 266, 369, 378, 398, 514, 727, 835, 939]

---

堆排序

import numpy as np# 大顶堆，从小到大排序def createHeap(lis,size):    for i in range(size/2)[::-1]:        adjust_Heap(lis,i,size)def adjust_Heap(lis,i,size):    # 因为i是中心得点靠左边的一个点，保证了它是最后一个根节点    lchild = 2*i + 1    rchild = 2*i + 2    max = i    if i < size/2:        if lchild < size and lis[lchild] > lis[max] :            max = lchild        if rchild < size and lis[rchild] > lis[max] :            max = rchild        if max != i:            # 则将最大值和该根节点交换位置            lis[max] , lis[i] = lis[i], lis[max]            # 调整了一个位置则需要将其子树进行重新堆排序            adjust_Heap(lis,max,size)if __name__ == "__main__" :    #lis = [1,3,9,0,2,8,5,6]    lis_ = np.random.randint(1,1000,10)    lis = list(lis_)    size = len(lis)    createHeap(lis,size)    # 每创造一次大顶堆排序，则选出首位为最大值，然后交换位置，继续排序    for i in range(size)[::-1]:        lis[0] , lis[i] = lis[i], lis[0]        adjust_Heap(lis,0,i)    print "before the sort ..."    print lis_    print "after the sort..."    print lis

输出结果：

before the sort ...[653 351 801 993 604 503 360 964 908 636]after the sort...[351, 360, 503, 604, 636, 653, 801, 908, 964, 993]

第二部分，时间性能的比较

转载地址：http://bliqi.baihongyu.com/