8大经典排序算法 Python3实现

博主： admin
发布时间：2017 年 02 月 24 日
637次浏览
暂无评论
5644字数
分类：算法coding

插入排序

插入排序是一种简单的排序法，把记录按照其关键字从小到大插入到前面已经排好的子序列中。

插入排序的思想，可以引出3个重要排序：直接插入排序，折半插入排序，希尔排序。

直接插入排序

直接插入法的思想是将L(2)~L(n)依次插入前面已经排好序的子序列里面，初始假设L(1)是排好序的子序列。根据上面的思想，一共执行n-1次操作，就能得到有序的表。通常，直接插入法使用L(0)作为哨兵，第一个数位置不放入元素。

有序系列L[1...i-1]

L[i]

无序序列L[i+1...n]

直接插入法的过程如下：

(1)找出$L(i)$在$l[1...i-1]$中的位置$k$

(2)将$L[k...i-1]$中的所有元素后移一个位置

(3)将$L(i)$复制到$L(k)$

插入排序是原地排序，直接插入法的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

可以通过这张图片来进一步理解：

直接插入排序Python代码(为了方便，我就不用哨兵了，而是用p来代替)。

Python实现如下：

def insertSort(A):
    for i in range(1,len(A)):
        if A[i-1] > A[i]:
            p = A[i]
            ''' 
            range的参数是 start, stop, step,范围是
            [start,stop)，所以stop参数是-1，而不是0
            '''
            for j in range(i-1,-1,-1):
                if A[j] < p:
                    '''因为Python的for没法进行逻辑判断，
                    所以只能先改变后判断，如果当前A[j]
                    的参数小于p，就要到回到j+1
                    '''
                    j += 1
                    break
                else:
                    A[j+1] = A[j]
            A[j] = p
    return A

折半插入排序

可以看出，直接插入排序有改善的空间，它需要一次次地比较才能找到最终要插入的位置,第$i$个位置的元素，最多要比较$i-1$次才能确定位置。既然前面的表是有序，可以使用二分查找法找到要插入的位置，然后统一地向后移动元素。

折半插入法的比较元素次数约为$O(nlog_2n)$，但仍然需要一个个地移动元素，所以时间复杂度还是$O(n^2)$。

Python实现如下：

def insertSort(A):
    for i in range(1,len(A)):
        p = A[i]
        low = 0
        high = i - 1
        while low <= high:
            middle = (low + high) // 2
            if A[middle] > p:
                high = middle - 1
            else:
                low = middle + 1
        for j in range(i-1,high,-1):
            A[j+1] = A[j]
        A[high + 1] = p
    return A

希尔排序

可以看出来，直接插入排序适合已经基本有序，或者数据量不大的列表。希尔排序法先对子表进行排序，然后再对整个数组进行排序。

希尔先将表分割成类似$L[i,i+d,i+2d,...,i+kd]$这种形式，然后进行直接插入排序，当它们"基本有序"之后，再对整体进行排序。

首先取一个小于$n$的步长$d_1$，分成$d_1$个组，再各个组中进行插入排序，之后取$d_{t+1}<d_t$，知道$d_t=1$的时候，直接对整个表进行一次插入排序。

目前没有较好的增量序列，希尔本人提出的方法是$d_1=n/2$，$d_{i+1}=\lfloor d_i/2\rfloor$，并最后一个增量等于1。

希尔排序的空间复杂度是$O(1)$，最坏的时候，时间复杂度仍然是$O(n^2)$。希尔排序是一个不稳定的排序法。

Python实现如下(这里有个坑，这次试用while来代替for，是在while执行的最后改变j的值，所以j-dk之后可能小于0，所以while中还要判断j是否小于0，如果小于0就不继续执行)：
微信端可能观看不到后面的代码，建议使用手机浏览器

def shellSort(A):
    n = len(A)
    dk = n
    while dk >=1:
        dk = dk // 2
        for i in range(dk+1,n):
            if A[i]<A[i-dk]:
                p = A[i]
                j = i-dk
                
                #由于使用 while 来代替 for，所以必须判断j是否小于k
                while j>=0 and A[j] > p:
                    A[j + dk] = A[j]
                    j = j - dk
                A[j+dk] = p
    return A

交换排序

交换排序的思想是根据序列中两个元素关键字比较的结果，来兑换这两个关键字。最著名的包括冒泡排序与快速排序。

冒泡排序

冒泡排序就是一个个地让A[i-1]与A[i]比较,每次把最小/最大的元素逐渐飘到最上/下面，所以叫冒泡排序。这样n-1次就OK了。

Python实现如下：

def bubbleSort(A):
    for i in range(0, len(A)-1,):
        flag = False
        for j in range(len(A)-1, i, -1):
            if A[j-1] > A[j]:
                A[j-1], A[j] = A[j], A[j-1]
                flag = True
        if not flag:
            return A

快速排序

快速排序是冒泡排序的改进版，基于分治法的思想。先选一个元素作为pivot，之后使pivot左边的值都小于它，右边的值都大于它。不断地二分就可以了。其实快速排序是可以并行运行的，选中了pivot的位置后，对pivot左右两个列表的排序可以同时进行。

快速排序的效率取决于划分是否对称。在基本有序，或者基本逆序的情况下效果很不好。

最坏的情况下时间复杂度是$O(n^2)$，最好的情况下空间复杂度是$O(n)$，平均情况下是$log_2n$。很明显，快速排序是不稳定排序。

Python实现如下：

def quickSort(A, low , high):
    print(A,low,high)
    if low < high:
        pivotpos,A = partition(A, low, high)
        print(A,0)
        A = quickSort(A,low,pivotpos-1)
        print(A,1)
        A = quickSort(A,pivotpos+1,high)
        print(A,2)
    return A

选择排序

选择排序思想是在第i趟，选择$L(i)$到$L(n)$上最小的元素，放到$L(i)$，这样$n-1$次就完成了所有的排序。

简单选择排序

简单选择排序方法，是根据选择排序的思想，第$i$趟选择关键字最小的元素跟$L(i)$交换，$n-1$次就可以完成整个表的排序。

下面这张动图非常好地诠释了这一过程：

选择排序

Python实现如下：

def selectSort(A):
    for i in range(0,len(A)-1):
        min = i
        for j in range(i+1,len(A)):
            if A[min] > A[j]:
                min = j
        if min != i:
            A[min], A[i] = A[i], A[min]
    return A

堆排序

堆排序是一种树形选择排序方法，把$L(1..n)$视为一棵完全二叉树的顺序存储结构。根据树形的思想，每次选择最大(最小)的元素。

堆的定义如下：

①$L(i)\le L(2i)$且$L(i)\le L(2i+1)$

或者

②$L(i)\ge L(2i)$且$L(i)\ge L(2i+1)$

满足①的堆被称为小顶堆，满足②的被称为大顶堆。

这里以小顶堆为例。堆排序的关键是建造初始的堆。是一个迭代过程。$n$个节点的完全二叉树，最后一个节点是第$\lfloor n/2\rfloor$个节点的孩子。对第$\lfloor n/2\rfloor$个节点为根的子树筛选，让该子树称为堆，之后再向前依次对$\lfloor n/2\rfloor$~$1$ 看该节点值是否大于其他子节点的值，如果大于，那么将左右子节点中的较大值与之交换，交换之后会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，知道该节点为根的子树构成堆为止。

Python实现如下：


def adjustDown(A, k, lens):
    A[0] = A[k]
    i = k
    while i * 2 <= lens:
        i *= 2
        if(i < lens and A[i] < A[i+1]):
            i += 1
        if A[0] >= A[i]:
            break
        else:
            A[k] = A[i]
            k = i
    A[k] = A[0]
    return A
def buildMaxHeap(A,lens):
    for i in range(lens//2, 0, -1):
        A = adjustDown(A,i,lens)
    return A

def heapSort(A,lens):
    A = buildMaxHeap(A,lens)
    for i in range(lens,0,-1):
        A[i],A[1] = A[1],A[i]
        A = adjustDown(A,1,i-1)
    return A

注意，调用的时候，应该给数组的0位置设置为空，从1开始存储，且长度为$len(A)-1$，具体调用例子如下：


A = [0,3,1,6,7,8,4,5,2]
heapSort(A,len(A)-1)

归并排序与基数排序

归并排序

归并排序的“归并”是指将两个，或两个或两个以上的有序表合为一个新的有序表。假设$L(1,..n)$这个表，归并排序吧它们当做$n$个有序表，然后两两归并，得到$\lceil n/2 \rceil$个长度为$2$或者$1$的表，之后再两两归并，知道合并成一个长度为$n$的表。

可以看出，归并排序是稳定的排序方法。每趟归并的时间复杂度是$O(n)$，一共需要$\lceil \log_2n\rceil$趟归并，所以时间复杂度一共是$O(n\log_2n)$。每次用来保存原始数组的，最多占用$n$个，所以空间复杂度是$O(n)$。

Python实现如下：

def merge(A1,A2):
    i = 0
    j = 0
    ret = []
    while i < len(A1) and j < len(A2):
        if A1[i] < A2[j]:
            ret.append(A1[i])
            i += 1
        else:
            ret.append(A2[j])
            j += 1
    if i<len(A1) > 0:
        ret.extend(A1[i:])
    if j<len(A2) > 0:
        ret.extend(A2[j:])
  
    return ret
    

def mergeSort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    A[:mid] = mergeSort(A[:mid])
    A[mid:] = mergeSort(A[mid:])
    A = merge(A[:mid], A[mid:])
    return A

基数排序

基数排序思想很简单，就是把数字先从个位排序，之后从十位排序，之后从百位排序。

但是，既然一个按位来排序，而每一位只有0~9这10个数，可以放10个数组，把该位的值，分配到对应的数组中。

这样一来，排序的时间复杂度就是$O(d(n+r))$，一趟分配要$O(n)$，一趟收集要$O(r)$。可以看出基数排序非常快，而且是稳定的。基数排序的空间复杂度为$O(r)$，也就是$r$个队列。

Python实现如下：

def radixSort(A):
    maxv = len("%d"%max(A))
    A = ["%d"%v for v in A]
    for d in range(maxv-1,-1,-1):
        bucket = dict()
        for i in range(10):
            bucket.setdefault(i,[])
        for v in A:
            bucket[int(v[d])].append(v)
        A=[]
        for i in range(10):
            A.extend(bucket[i])
    return [int(v) for v in A]

各种排序的比较：

算法种类	时间复杂度(最好)	评价	最坏	空间复杂度	是否稳定
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
简单选择排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	否
希尔排序	---	----	----	$O(\log_2n)$	否
快速排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n^2)$	$O(\log_2n)$	否
堆排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	否
2路归并排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	是
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	是

最后修改：2021 年 06 月 01 日 02 : 06 PM

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

8大经典排序算法 Python3实现

admin • 2017 年 02 月 24 日

插入排序

插入排序是一种简单的排序法，把记录按照其关键字从小到大插入到前面已经排好的子序列中。

插入排序的思想，可以引出3个重要排序：直接插入排序，折半插入排序，希尔排序。

直接插入排序

有序系列L[1...i-1]

L[i]

无序序列L[i+1...n]

直接插入法的过程如下：

(1)找出$L(i)$在$l[1...i-1]$中的位置$k$

(2)将$L[k...i-1]$中的所有元素后移一个位置

(3)将$L(i)$复制到$L(k)$

插入排序是原地排序，直接插入法的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

可以通过这张图片来进一步理解：

直接插入排序Python代码(为了方便，我就不用哨兵了，而是用p来代替)。

Python实现如下：

def insertSort(A):
    for i in range(1,len(A)):
        if A[i-1] > A[i]:
            p = A[i]
            ''' 
            range的参数是 start, stop, step,范围是
            [start,stop)，所以stop参数是-1，而不是0
            '''
            for j in range(i-1,-1,-1):
                if A[j] < p:
                    '''因为Python的for没法进行逻辑判断，
                    所以只能先改变后判断，如果当前A[j]
                    的参数小于p，就要到回到j+1
                    '''
                    j += 1
                    break
                else:
                    A[j+1] = A[j]
            A[j] = p
    return A

折半插入排序

折半插入法的比较元素次数约为$O(nlog_2n)$，但仍然需要一个个地移动元素，所以时间复杂度还是$O(n^2)$。

Python实现如下：

def insertSort(A):
    for i in range(1,len(A)):
        p = A[i]
        low = 0
        high = i - 1
        while low <= high:
            middle = (low + high) // 2
            if A[middle] > p:
                high = middle - 1
            else:
                low = middle + 1
        for j in range(i-1,high,-1):
            A[j+1] = A[j]
        A[high + 1] = p
    return A

希尔排序

可以看出来，直接插入排序适合已经基本有序，或者数据量不大的列表。希尔排序法先对子表进行排序，然后再对整个数组进行排序。

希尔先将表分割成类似$L[i,i+d,i+2d,...,i+kd]$这种形式，然后进行直接插入排序，当它们"基本有序"之后，再对整体进行排序。

首先取一个小于$n$的步长$d_1$，分成$d_1$个组，再各个组中进行插入排序，之后取$d_{t+1}<d_t$，知道$d_t=1$的时候，直接对整个表进行一次插入排序。

目前没有较好的增量序列，希尔本人提出的方法是$d_1=n/2$，$d_{i+1}=\lfloor d_i/2\rfloor$，并最后一个增量等于1。

希尔排序的空间复杂度是$O(1)$，最坏的时候，时间复杂度仍然是$O(n^2)$。希尔排序是一个不稳定的排序法。

def shellSort(A):
    n = len(A)
    dk = n
    while dk >=1:
        dk = dk // 2
        for i in range(dk+1,n):
            if A[i]<A[i-dk]:
                p = A[i]
                j = i-dk
                
                #由于使用 while 来代替 for，所以必须判断j是否小于k
                while j>=0 and A[j] > p:
                    A[j + dk] = A[j]
                    j = j - dk
                A[j+dk] = p
    return A

交换排序

交换排序的思想是根据序列中两个元素关键字比较的结果，来兑换这两个关键字。最著名的包括冒泡排序与快速排序。

冒泡排序

冒泡排序就是一个个地让A[i-1]与A[i]比较,每次把最小/最大的元素逐渐飘到最上/下面，所以叫冒泡排序。这样n-1次就OK了。

Python实现如下：

def bubbleSort(A):
    for i in range(0, len(A)-1,):
        flag = False
        for j in range(len(A)-1, i, -1):
            if A[j-1] > A[j]:
                A[j-1], A[j] = A[j], A[j-1]
                flag = True
        if not flag:
            return A

快速排序

快速排序的效率取决于划分是否对称。在基本有序，或者基本逆序的情况下效果很不好。

最坏的情况下时间复杂度是$O(n^2)$，最好的情况下空间复杂度是$O(n)$，平均情况下是$log_2n$。很明显，快速排序是不稳定排序。

Python实现如下：

def quickSort(A, low , high):
    print(A,low,high)
    if low < high:
        pivotpos,A = partition(A, low, high)
        print(A,0)
        A = quickSort(A,low,pivotpos-1)
        print(A,1)
        A = quickSort(A,pivotpos+1,high)
        print(A,2)
    return A

选择排序

选择排序思想是在第i趟，选择$L(i)$到$L(n)$上最小的元素，放到$L(i)$，这样$n-1$次就完成了所有的排序。

简单选择排序

简单选择排序方法，是根据选择排序的思想，第$i$趟选择关键字最小的元素跟$L(i)$交换，$n-1$次就可以完成整个表的排序。

下面这张动图非常好地诠释了这一过程：

选择排序

Python实现如下：

def selectSort(A):
    for i in range(0,len(A)-1):
        min = i
        for j in range(i+1,len(A)):
            if A[min] > A[j]:
                min = j
        if min != i:
            A[min], A[i] = A[i], A[min]
    return A

堆排序

堆排序是一种树形选择排序方法，把$L(1..n)$视为一棵完全二叉树的顺序存储结构。根据树形的思想，每次选择最大(最小)的元素。

堆的定义如下：

①$L(i)\le L(2i)$且$L(i)\le L(2i+1)$

或者

②$L(i)\ge L(2i)$且$L(i)\ge L(2i+1)$

满足①的堆被称为小顶堆，满足②的被称为大顶堆。

Python实现如下：


def adjustDown(A, k, lens):
    A[0] = A[k]
    i = k
    while i * 2 <= lens:
        i *= 2
        if(i < lens and A[i] < A[i+1]):
            i += 1
        if A[0] >= A[i]:
            break
        else:
            A[k] = A[i]
            k = i
    A[k] = A[0]
    return A
def buildMaxHeap(A,lens):
    for i in range(lens//2, 0, -1):
        A = adjustDown(A,i,lens)
    return A

def heapSort(A,lens):
    A = buildMaxHeap(A,lens)
    for i in range(lens,0,-1):
        A[i],A[1] = A[1],A[i]
        A = adjustDown(A,1,i-1)
    return A

注意，调用的时候，应该给数组的0位置设置为空，从1开始存储，且长度为$len(A)-1$，具体调用例子如下：


A = [0,3,1,6,7,8,4,5,2]
heapSort(A,len(A)-1)

归并排序与基数排序

归并排序

Python实现如下：

def merge(A1,A2):
    i = 0
    j = 0
    ret = []
    while i < len(A1) and j < len(A2):
        if A1[i] < A2[j]:
            ret.append(A1[i])
            i += 1
        else:
            ret.append(A2[j])
            j += 1
    if i<len(A1) > 0:
        ret.extend(A1[i:])
    if j<len(A2) > 0:
        ret.extend(A2[j:])
  
    return ret
    

def mergeSort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    A[:mid] = mergeSort(A[:mid])
    A[mid:] = mergeSort(A[mid:])
    A = merge(A[:mid], A[mid:])
    return A

基数排序

基数排序思想很简单，就是把数字先从个位排序，之后从十位排序，之后从百位排序。

但是，既然一个按位来排序，而每一位只有0~9这10个数，可以放10个数组，把该位的值，分配到对应的数组中。

Python实现如下：

def radixSort(A):
    maxv = len("%d"%max(A))
    A = ["%d"%v for v in A]
    for d in range(maxv-1,-1,-1):
        bucket = dict()
        for i in range(10):
            bucket.setdefault(i,[])
        for v in A:
            bucket[int(v[d])].append(v)
        A=[]
        for i in range(10):
            A.extend(bucket[i])
    return [int(v) for v in A]

各种排序的比较：

算法种类	时间复杂度(最好)	评价	最坏	空间复杂度	是否稳定
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
简单选择排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	否
希尔排序	---	----	----	$O(\log_2n)$	否
快速排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n^2)$	$O(\log_2n)$	否
堆排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	否
2路归并排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	是
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	是

8大经典排序算法 Python3实现

插入排序

直接插入排序

折半插入排序

交换排序

冒泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序与基数排序

归并排序

基数排序

发表评论取消回复

广义拉格朗日函数及其对偶算法

支持向量机SVM 系列(1)——线性可分支持向量机

支持向量机SVM 系列(2)——对偶方法(Dual Method)

支持向量机SVM 系列(3)——核函数(Kernel Function)

支持向量机SVM 系列(4)——软间隔(soft-margin SVM)

Python 调用 Docker 及推送至AWS ECR

《PRML》读书笔记概率论、贝叶斯线性拟合

LightGBM与XGBoost K-Flod训练预测模板

Hadoop学习记录2：MapReduce基础原理

SQL语句不完全总结

8大经典排序算法 Python3实现

插入排序

直接插入排序

折半插入排序

交换排序

冒泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序与基数排序

归并排序

基数排序

插入排序

直接插入排序

折半插入排序

交换排序

冒泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序与基数排序

归并排序

基数排序

发表评论 取消回复

8大经典排序算法 Python3实现

插入排序

直接插入排序

折半插入排序

交换排序

冒泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序与基数排序

归并排序

基数排序

发表评论取消回复