排序算法概述

在本系列中我们综述十个常用排序算法，分别是简单插入排序、希尔排序、简单选择排序、快速排序、冒泡排序、堆排序、归并排序、计数排序、桶排序、基数排序。此外，针对快速排序算法，额外介绍了基于单链表的快速排序算法。整体框架如下：

排序算法概览

---

基于插入思想

这里我们介绍简单插入排序已经希尔排序。

• • 简单插入排序
• 思想
  开始时默认第一个数有序，将剩余n-1个数逐个插入。插入操作具体包括：比较确定插入位置，数据移位腾出合适空位。每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。额外空间开销出在数据移位时那一个过渡空间，空间复杂度O(1)。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n^2)
# 空间复杂度：o(1)
# 稳定性：稳定

'''
简单插入排序同样操作n-1轮，每轮将一个未排序树插入排好序列。

开始时默认第一个数有序，将剩余n-1个数逐个插入。插入操作具体包括：比较确定插入位置，数据移位腾出合适空位

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在数据移位时那一个过渡空间，空间复杂度O(1)。
'''
from typing import List
class Solution:
    def InsertSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj

        for i in range(1, len(obj)):
            j = i
            target = obj[j]     # target是将要进行比较的元素
            # 这里是>0而不是>=0，因为obj[j]要和j前一位数字进行比较，所以j最小只能是1，否则下面的obj[j-1]会数组越界
            while j>0 and target<obj[j-1]:
                obj[j] = obj[j-1]   # 所有大于target的元素后移
                j -= 1
            # 最后直到找到一位j，使得obj[j] > obj[j-1]或者j为0
            obj[j] = target

        return obj


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.InsertSort(obj)
    print(res)

• • 希尔排序
• 思想
  希尔排序是插入排序的高效实现，对简单插入排序减少移动次数优化而来。本质是还是插入排序。
  希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。希尔排序对序列划分O(n)次，每次简单插入排序O(logn)，时间复杂度O(nlogn)
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n*log(n))
# 空间复杂度：o(1)
# 稳定性：不稳定

'''
希尔排序是插入排序的高效实现，对简单插入排序减少移动次数优化而来。

简单插入排序每次插入都要移动大量数据，前后插入时的许多移动都是重复操作，若一步到位移动效率会高很多。

若序列基本有序，简单插入排序不必做很多移动操作，效率很高。

希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。

希尔排序对序列划分O(n)次，每次简单插入排序O(logn)，时间复杂度O(nlogn)

额外空间开销出在插入过程数据移动需要的一个暂存，空间复杂度O(1)
希尔排序会设置一个增量，初始增量设为待排序样本长度的一半，即 gap = length//2 ，之后每一次增量为前一次的一半，即 gap = gap//2
当增量减至1时，整个文件恰被分成一组，算法便终止。
'''
from typing import List
class Solution:
    def ShellSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        gap = len(obj) >> 1

        while gap > 0:
            for i in range(gap, len(obj)):
                target = obj[i]
                j = i-gap
                while(j>=0 and target<obj[j]):
                    obj[j+gap] = obj[j]
                    j -= gap
                obj[j+gap] = target
            gap >>= 1
        return obj


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.ShellSort(obj)
    print(res)

基于选择思想

• • 简单选择排序
• 思想
  简单选择排序同样对数据操作n-1轮，每轮找出一个最大（小）值。操作指选择，即未排序数逐个比较交换，争夺最值位置，每轮将一个未排序位置上的数交换成已排序数，即每轮选一个最值。每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n^2)
# 空间复杂度：o(1)
# 稳定性：稳定

'''
简单选择排序同样对数据操作n-1轮，每轮找出一个最大（小）值。

操作指选择，即未排序数逐个比较交换，争夺最值位置，每轮将一个未排序位置上的数交换成已排序数，即每轮选一个最值。

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
'''
from typing import List
class Solution:
    def SelectSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj

        # 因为对于选择排序，排到最后一个元素的时候不用算hhhh，所以就len(obj)-1 就行
        for i in range(len(obj)-1):
            minIndex = i
            for j in range(i+1, len(obj)):
                if obj[j] < obj[minIndex]:
                    minIndex = j
            if minIndex != i:
                obj[i], obj[minIndex] = obj[minIndex], obj[i]
        return obj


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.SelectSort(obj)
    print(res)

• • 快速排序
• 思想
  快速排序基于选择划分，是简单选择排序的优化。每次划分将数据选到基准值两边，循环对两边的数据进行划分，类似于二分法。算法的整体性能取决于划分的平均程度，即基准值的选择，此处衍生出快速排序的许多优化方案，甚至可以划分为多块。基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n*log(n))
# 空间复杂度：o(log(n))
# 稳定性：不稳定

'''
快速排序基于选择划分，是简单选择排序的优化。

每次划分将数据选到基准值两边，循环对两边的数据进行划分，类似于二分法。

算法的整体性能取决于划分的平均程度，即基准值的选择，此处衍生出快速排序的许多优化方案，甚至可以划分为多块。

基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。

额外空间开销出在暂存基准值，O(logn)次划分需要O(logn)个，空间复杂度O(logn) （因为是递归形式的，因此所有基准值都要存储）

'''
from typing import List
class Solution:
    def QuickSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj

        # 因为快速排序是基于递归思想的，因此我们还要再定义一个函数
        def quick_sort(q, l, r):
            if l >= r:
                return
            x = q[(l + r)>>1]
            i, j = l - 1, r + 1
            while (i < j):
                while True:
                    i += 1
                    if q[i] > x:
                        break
                while True:
                    j -= 1
                    if q[j] < x:
                        break
                if i < j:
                    q[i], q[j] = q[j], q[i]

            quick_sort(q, l, j)
            quick_sort(q, j + 1, r)

        quick_sort(obj, 0, len(obj)-1)
        return obj


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.QuickSort(obj)
    print(res)

• • 快速排序的单链表形式
• 思想
  与快速排序一样，基于链表的结构使得快速排序变成稳定排序，即元素前后顺序不会更改。
• 代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

'''
给定一个单链表，请使用快速排序算法对其排序。

要求：期望平均时间复杂度为 O(nlogn)，期望额外空间复杂度为 O(logn)。

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

数据范围
链表中的所有数大小均在 int 范围内，链表长度在 [0,10000]。

输入样例：
[5, 3, 2]
输出样例：
[2, 3, 5]
'''
# 快速排序的单链表形式，时间和空间复杂度与普通快排相同，但是优点是可以保留原有顺序，是稳定的排序方式
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def quickSortList(self, head: ListNode):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        left = ListNode(-1) ; mid = ListNode(-1)    ; right = ListNode(-1)
        ltail = left        ; mtail = mid           ; rtail = right
        target = head.val
        p = head
        while p:
            if p.val < target:
                ltail.next = p
                ltail = p
            elif p.val == target:
                mtail.next = p
                mtail = p
            else:
                rtail.next = p
                rtail = p
            p = p.next
        ltail.next = None; mtail.next = None; rtail.next = None
        left.next = self.quickSortList(left.next)
        right.next = self.quickSortList(right.next)
        self.get_tail(left).next = mid.next
        self.get_tail(left).next = right.next
        return left.next

    def get_tail(self, head: ListNode):
        while head and head.next:
            head = head.next
        return head

基于交换思想

• • 冒泡排序
• 思想
  冒泡排序对数据操作n-1轮，每轮找出一个最大（小）值。操作指对相邻两个数比较与交换，每轮会将一个最值交换到数据列首（尾），像冒泡一样。每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n^2)
# 空间复杂度：o(1)
# 稳定性：稳定

'''
冒泡排序对数据操作n-1轮，每轮找出一个最大（小）值。

操作指对相邻两个数比较与交换，每轮会将一个最值交换到数据列首（尾），像冒泡一样。

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
'''
from typing import List
class Solution:
    def BubbleSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        for i in range(len(obj)):
            for j in range(len(obj)-i-1):
                if obj[j] > obj[j+1]:
                    obj[j], obj[j+1] = obj[j+1], obj[j]
        return obj


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.BubbleSort(obj)
    print(res)

• • 堆排序
• 思想
  堆排序基于比较交换，是冒泡排序的优化。具体涉及大（小）顶堆的建立与调整。大顶堆指任意一个父节点都不小于左右两个孩子节点的完全二叉树，根节点最大。堆排序首先建立大顶堆（找出一个最大值），然后用最后一个叶子结点代替根节点后做大顶堆的调整（再找一个最大值），重复此操作，直到将数列按由大到小的顺序找完。
  这里需要注意两个公式，在以列表形式表现的完全二叉树中，节点n的左、右孩子编号分别为2*n+1，2*n+2，节点n的父亲编号为(n-1)//2（节点从0开始编号）
  堆排序有两个核心步骤：①建堆（根据定义建堆，即每个父节点的值>=子节点） ②依照建好的堆，依次读取堆顶元素，具体的做法是将堆顶元素与末尾元素交换（相当于把堆顶元素放到答案空间），然后对新的堆进行再一次调整。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n*log(n))
# 空间复杂度：o(1)
# 稳定性：不稳定
# 注意：初始建堆时间复杂度O(n)，一次重建堆时间复杂度O(logn)，所以如果对整个长为n的数组进行排序，时间复杂度是 o(n + n*log(n)) = o(n*log(n))

'''
堆排序基于比较交换，是冒泡排序的优化。具体涉及大（小）顶堆的建立与调整。

大顶堆指任意一个父节点都不小于左右两个孩子节点的完全二叉树，根节点最大。

堆排序首先建立大顶堆（找出一个最大值），然后用最后一个叶子结点代替根节点后做大顶堆的调整（再找一个最大值），重复

以数组（列表）实现大顶堆时，从上到下，从左到右编号。父节点序号为n，则左右孩子节点序号分别为2*n+1、2*n+2

大顶堆的调整：将仅有根节点不满足条件的完全二叉树，调整为大顶堆的过程。

大顶堆调整方法：将根节点与较大一个儿子节点比较，不满足条件则交换。
若发生交换，将被交换儿子节点视作根节点重复上一步

大顶堆的建立：从最后一个非叶子节点开始到根节点结束的一系列大顶堆调整过程。

堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)

额外空间开销出在调整堆过程，根节点下移交换时一个暂存空间，空间复杂度O(1)

'''
# 堆排序特点 ①：必须是一棵完全二叉树  ②：父节点的值 > 子节点的值
# 所以，堆排序的第一步就是建堆。如何建堆呢？那就让堆符合我们的定义，即：父节点的值 > 子节点的值

# 堆排序总共有两大步骤： ①建堆，这一步是o(n)的时间复杂度  ②依照建好的堆，一次读取堆顶元素，具体的做法是将堆顶元素与末尾元素交换
# 每一次交换后都要对新堆进行微调，使其达到要求（满足堆的定义），这里每一步是o(log(n))的复杂度，一共n次
# 一个公式是，节点i的子节点，序号是 2*i+1, 2*i+2， 节点i的父节点，序号是 (i-1)>>1
from typing import List
class Solution:
    def HeapSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        n = len(obj)

        def heapify(n, i):
            # heapify(i)表示对第i个节点进行heapify操作，即使以i节点为根节点的树符合堆的特性
            if i > n:
                return

            c1 = 2*i+1
            c2 = 2*i+2
            max_ = i
            if c1<n and obj[c1]>obj[max_]:
                max_ = c1
            if c2<n and obj[c2]>obj[max_]:
                max_ = c2
            if max_ != i:
                obj[i], obj[max_] = obj[max_], obj[i]
                heapify(n, max_)

        def build_heap(n):
            last_node = n-1
            parent = (last_node-1) >> 1
            for i in range(parent, -1, -1):
                heapify(n, i)

        def heap_sort():
            build_heap(n)
            for i in range(n-1, -1, -1):
                obj[i], obj[0] = obj[0], obj[i]
                heapify(i, 0)

        build_heap(n)
        heap_sort()
        return obj



if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.HeapSort(obj)
    print(res)

基于分治思想

分治排序

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

• • 归并排序
• 思想
  归并排序运用分治递归思想：将大问题分为较小的子问题，分而治之；递归调用同样的方法解决子问题。最终将序列的排序问题分治为一个数的排序问题，关键在于如何将子问题答案合并为问题答案。两个有序序列合并为一个有序序列，借助一个暂存数组（列表），两个序列元素依次比较填入暂存列表，形成一个有序序列。归并排序划分子问题采用二分法，共需O(log(n))次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(n*log(n))。额外空间开销出在合并过程中的一个暂存数组，空间复杂度O(n)。归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9

# 时间复杂度：o(n*log(n))
# 空间复杂度：o(n)
# 稳定性：稳定

'''
归并排序运用分治递归思想：将大问题分为较小的子问题，分而治之；递归调用同样的方法解决子问题。最终将序列的排序问题分治为一个数的排序问题，关键在于如何将子问题答案合并为问题答案。

两个有序序列合并为一个有序序列，借助一个暂存数组（列表），两个序列元素依次比较填入暂存列表，形成一个有序序列。

归并排序划分子问题采用二分法，共需O(log(n))次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(n*log(n))。

额外空间开销出在合并过程中的一个暂存数组，空间复杂度O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
'''
from typing import List
class Solution:
    def MergeSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        mid = (len(obj)) >> 1
        left = self.MergeSort(obj[:mid])
        right = self.MergeSort(obj[mid:])
        res = []
        while left and right:
            if left[0] <= right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        if left:
            # 注意这里要用 extend，不然会出现形如[3, 4, [5], 7]的情况
            res.extend(left)
        elif right:
            res.extend(right)
        return res


if __name__ == '__main__':
    x = input("请输入待排序数列：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.MergeSort(obj)
    print(res)

基于桶思想

• • 计数排序
• 思想
  计数排序可以说是桶排序的一种特殊情况，当排序n个数据时，n的取值范围很小的时候，比如说是0-k，我们就可以分成k个桶，因为桶内的数据都是一致的，所以可以减少了桶内排序的时间。 举个例子，对高考成绩省内排名，成绩仅是一个三位数区间，我们就可以用这种方法。

• 例子
  一组学生的成绩为{2，5，3，0，2，3，0，3},这时候我们可以用一个数组A[8]存储这组数据，然后按照桶排序的标准，将数据分成0-5，建立一个初始化的数组C[6]表示桶,然后遍历一遍A[8],得到一个新的C[6]

  
  计数排序
  

  从图中可以看出分数为3的有3人，小于3的分数有4人，所以可以得出一个R[8]

  
  
  如何快速确认成绩在数组中的位置呢，当然不能通过我们肉眼看，我们的思路是进行对C[6]进行一次顺序求和，所以C[6]的存储情况变成了如下：
  
• 总结：
  计数排序利于数据可视化，非常适用于待排序数列分布集中的场景，局限是计数排序需要保证待排序数为整数，对于带有小数位的数列排列时，解法方法是可以先对其整数位进行排序，得到基本有序的数列，接着对于桶内每一个元素，再进行进一步排序，如快排，希尔排序或堆排序、归并排序等时间复杂度为o(n*log(n))的操作。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/10

# 时间复杂度：o(n + k)
# 空间复杂度：o(k)
# 稳定性：稳定
# n：数据规模 ；k：‘桶’个数

'''
计数排序用待排序的数值作为计数数组（列表）的下标，统计每个数值的个数，然后依次输出即可。

计数数组的大小取决于待排数据取值范围，所以对数据有一定要求，否则空间开销无法承受。

计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。

额外空间开销即指计数数组，实际上按数据值分为k类（大小取决于数据取值），空间复杂度O(k)。
注意： 计数排序只能用在所有元素均整数的情况下，而且计数排序的取值范围最好不要太大.
'''
from typing import List
class Solution:
    def CountSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        min_num = min(obj)
        max_num = max(obj)
        count = [0]*(max_num - min_num + 1)
        for i in obj:
            count[i - min_num] += 1

        res = []
        for i in range(len(count)):
            if count[i] > 0:
                res.extend([i+min_num]*count[i])
        return res

if __name__ == '__main__':
    x = input("请输入待排序数列，所有元素必须为整数：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.CountSort(obj)
    print(res)

• • 桶排序
• 思想
  相当于对计数排序做了一个改进：先用一定的函数关系将数据划分到不同有序的区域（桶）内，然后子数据分别在桶内排序（如快速排序、归并排序等等），之后顺次输出。当每一个不同数据分配一个桶时，也就相当于计数排序。
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/10

# 时间复杂度：o(n + k)
# 空间复杂度：o(n + k)
# 稳定性：稳定
# n：数据规模 ；k：‘桶’个数

'''
桶排序实际上是计数排序的推广，但实现上要复杂许多。

桶排序先用一定的函数关系将数据划分到不同有序的区域（桶）内，然后子数据分别在桶内排序，之后顺次输出。

当每一个不同数据分配一个桶时，也就相当于计数排序。

假设n个数据，划分为k个桶，桶内采用快速排序，时间复杂度为O(n)+O(k * n/k*log(n/k))=O(n)+O(n*(log(n)-log(k))),

显然，k越大，时间复杂度越接近O(n)，当然空间复杂度O(n+k)会越大，这是空间与时间的平衡。
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序
'''
from typing import List
class Solution:
    def BucketSort(self, obj: List[int]):
        res = []
        if len(obj) <= 1:
            return obj
        # 假设一共设10个桶
        k = 10
        min_num = min(obj)
        max_num = max(obj)
        space = (max_num - min_num) // k
        bucket = [[] for _ in range(k+1)]
        for i in obj:
            bucket[(i-min_num)//space].append(i)
        for sub_bucket in bucket:
            self.QuickSort(sub_bucket)
            res.extend(sub_bucket)
        return res


    def QuickSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj

        # 因为快速排序是基于递归思想的，因此我们还要再定义一个函数
        def quick_sort(q, l, r):
            if l >= r:
                return
            x = q[(l + r)>>1]
            i, j = l - 1, r + 1
            while (i < j):
                while True:
                    i += 1
                    if q[i] > x:
                        break
                while True:
                    j -= 1
                    if q[j] < x:
                        break
                if i < j:
                    q[i], q[j] = q[j], q[i]

            quick_sort(q, l, j)
            quick_sort(q, j + 1, r)

        quick_sort(obj, 0, len(obj)-1)
        return obj

if __name__ == '__main__':
    x = input("请输入待排序数列，所有元素必须为整数：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.BucketSort(obj)
    print(res)

• • 基数排序
• 思想
  基数排序进行多轮按位比较排序，轮次取决于最大数据值的位数。先按照个位比较排序，然后十位百位以此类推，优先级由低到高，这样后面的移动就不会影响前面的。基数排序按位比较排序实质上也是一种划分，一种另类的‘桶’罢了。比如，第一轮按各个位比较，按个位大小排序分别装入10个‘桶’中，‘桶’中个位相同的数据视作相等，桶是有序的，按序输出，后面轮次接力完成排序。基数排序‘桶’内数据在划分桶时便已排序O(n)，k个桶，时间复杂度为O(n*k)。额外空间开销出在数据划分入桶过程，桶大小O(n+k)，空间复杂度O(n+k)。事实上，这里我们k通常是10个，也就是位数从0到9
• Python3代码

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/10

# 时间复杂度：o(n * k)
# 空间复杂度：o(n+k)
# 稳定性：稳定
# n：数据规模 ；k：‘桶’个数

'''
基数排序进行多轮按位比较排序，轮次取决于最大数据值的位数。

先按照个位比较排序，然后十位百位以此类推，优先级由低到高，这样后面的移动就不会影响前面的。

基数排序按位比较排序实质上也是一种划分，一种另类的‘桶’罢了。比如，第一轮按各个位比较，按个位大小排序分别装入10个‘桶’中，‘桶’中个位相同的数据视作相等，桶是有序的，按序输出，后面轮次接力完成排序。

基数排序‘桶’内数据在划分桶时便已排序O(n)，k个桶，时间复杂度为O(n*k)。

额外空间开销出在数据划分入桶过程，桶大小O(n+k)，空间复杂度O(n+k)。
事实上，这里我们k通常是10个，也就是位数从0到9
'''
from typing import List
class Solution:
    def RadixSort(self, obj: List[int]):
        if len(obj) <= 1:
            return obj
        radix = 10
        K = len(str(max(obj)))  # K表示最大位数
        for i in range(1, K+1):
            bucket = [[] for _ in range(10)]    # 不能用 [[]]*radix，否则相当于开了radix个完全相同的list对象
            for val in obj:
                bucket[val%(radix**i) // (radix**(i-1))].append(val)    # 这是为了得到val的第i位的数字
            obj = []
            for each in bucket:
                obj.extend(each)
        return obj

if __name__ == '__main__':
    x = input("请输入待排序数列，所有元素必须为整数：\n")
    obj = list(map(int, x.split()))
    solution = Solution()
    res = solution.RadixSort(obj)
    print(res)

总结

1.存在即有理。十种排序算法在时间、空间复杂度，实现难度，稳定性等指标上存在较大差异，但并没有最好最坏之说，适合的才是最好的。

2.三种O(n^2)平均时间复杂度的排序算法在空间复杂度、稳定性方面表现较好，甚至在特定情况下即便考虑时间复杂度也是最佳选择。

3.堆排序初始建堆过程较复杂，仅建堆时间复杂度就达到O(nlogn)，但之后的排序开销稳定且较小，所以适合大量数据排序。

4.希尔排序性能看似很好，但实际上他的整体性能受步长选取影响较大，插入排序本质也使他受数据影响较大。

5.归并排序在平均和最坏情况下时间复杂度都表现良好O(nlogn)，但昂贵的空间开销大O(n)。

6.快速排序大名鼎鼎，又有个好名字，但最坏情况下时间复杂度直逼O(n^2)，远不如堆排序和归并排序。

7.基于比较排序的算法（如前七种）时间复杂度O(nlogn)已是下限。

8.三种线性时间复杂度排序算法虽然在速度上有决定性的优势，但也付出了沉重的空间代价，有时数据的特点让这种空间代价变得无法承受。所以他们的应用对数据本身有着特定的要求。

9.关于稳定性，希尔排序、快速排序和堆排序这三种排序算法无法保障。三种算法因为划分（子序列、大小端、左右孩子）后各自处理无法保证等值数据的原次序。

参考资料：
aiya_aiya_的CSDN博客
堆排序_Youtube，作者黄浩杰，B站搜 '正月点灯笼'
堆排序_Wikipedia
归并排序_Wikipedia
基数排序_Wikipedia