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

0 前言

昨天做题发现对排序算法说懂又很模糊，说不懂又知道。所以今天强化下记忆。

1 类别

从上图可以看出主要分两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 

因此本文也按照上面分类来一一描述经典的分类算法

2  交换排序

2.1 冒泡排序

冒泡排序重复走访要排序的数列，一次比较两个元素，如果顺序出错就交换。知道没有再需要交换为止。

算法描述：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

图示：

代码实现（python）：

L=[10,7,5,2,8,3]def bubble_sort(L):    count=len(L)    for i in range(0,count):        for j in range(i+1,count):            if L[i]>L[j]:                L[i],L[j]=L[j],L[i]    return Lprint(bubble_sort(L))

2.2 快速排序

基本思想：分而治之，选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。

算法描述：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

图示：

代码实现（python）：

def QuickSort(myList,start,end):    #判断low是否小于high,如果为false,直接返回    if start < end:        i,j = start,end        #设置基准数        base = myList[i]        while i < j:            #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现            while (i < j) and (myList[j] >= base):                j = j - 1            #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等            myList[i] = myList[j]            #同样的方式比较前半区            while (i < j) and (myList[i] <= base):                i = i + 1            myList[j] = myList[i]        #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base        myList[i] = base        #递归前后半区        QuickSort(myList, start, i - 1)        QuickSort(myList, j + 1, end)    return myListmyList = [49,38,65,97,76,13,27,49]print("Quick Sort: ")QuickSort(myList,0,len(myList)-1)print(myList)

3 插入排序

3.1 直接插入排序

通过构建有序序列，对于未排序数据，在已排序序列从后向前扫描，找到相应的位置插入

算法描述：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

图示：

代码实现（python）：

def insertSort(arr):    length = len(arr)    for i in range(1,length):        x = arr[i]        j=i-1        while j>=0:            if x < arr[j]:                arr[j+1] = arr[j]                arr[j]=x            j-=1def printArr(arr):     print(arr)arr = [4, 7 ,8 ,2 ,3 ,5]insertSort(arr)printArr(arr)

3.2 希尔排序

希尔排序又叫缩小增量排序，是简单插入排序的改进版，不同之处在于它会优先比较距离较远的元素

算法描述：

先将整个待排序的记录序列分割成若干子序列分别进行插入排序

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

图示：

 

代码实现（python）

def shell_sort(lists):    # 希尔排序    count = len(lists)    step = 2    group = count / step    while group > 0:        for i in range(0, group):            j = i + group            while j < count:                k = j - group                key = lists[j]                while k >= 0:                    if lists[k] > key:                        lists[k + group] = lists[k]                        lists[k] = key                    k -= group                j += group        group /= step    return lists

4 选择排序

4.1  简单选择排序

选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置作为已排序序列，然后，再从剩余排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；以此类推，直到所有元素均排序完毕。

算法描述：

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

图示：

代码实现（python）

def select_sort(lists):    # 选择排序    count = len(lists)    for i in range(0, count):        min = i        for j in range(i + 1, count):            if lists[min] > lists[j]:                min = j        lists[min], lists[i] = lists[i], lists[min]    return lists

4.2 堆排序

堆排序(Heapsort)是利用堆这种数据结构设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子节点的键值或索引总是小于（或者大于）它的父节点。

注：这个前提要弄明白堆 ，推荐链接：

算法描述：

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

图示：

代码实现（python）

def adjust_heap(lists, i, size):    lchild = 2 * i + 1    rchild = 2 * i + 2    max = i    if i < size / 2:        if lchild < size and lists[lchild] > lists[max]:            max = lchild        if rchild < size and lists[rchild] > lists[max]:            max = rchild        if max != i:            lists[max], lists[i] = lists[i], lists[max]            adjust_heap(lists, max, size) def build_heap(lists, size):    for i in range(0, (size/2))[::-1]:        adjust_heap(lists, i, size) def heap_sort(lists):    size = len(lists)    build_heap(lists, size)    for i in range(0, size)[::-1]:        lists[0], lists[i] = lists[i], lists[0]        adjust_heap(lists, 0, i)

 

5 归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法描述：

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

图示：

代码实现（python）：二路归并

def merge_sort(lists):    if len(lists)<=1:        return lists    num=len(lists)//2    left=merge_sort(lists[:num])    right=merge_sort(lists[num:])    return merge(left,right)def merge(left,right):    i,j=0,0    result=[]    while i

 

6 基数排序

基数排序（radix sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述：

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

图示：

 

代码实现（python） ：

import mathdef radix_sort(lists,radix=10):    '''        math.ceil 为x取整，结果是不小于x的最小整数.        math.log(x, a)  返回 log 以 a 为底 x 的对数，若不给定 a 则底默认为 e    '''    k=int(math.ceil(math.log(max(lists),radix)))    bucket=[[]for i in range(radix)]    for i in range(1,k+1):        for j in lists:            bucket[math.floor(j / (radix ** (i - 1)) % (radix))].append(j)            #删除列表中所有元素        del list[:]        for z in bucket:            lists+=z            del z[:]    return listslist = [434,24,657,976,2354,9,67,8099,4353,3453]print(radix_sort(list))

 

 

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