Python 实现经典排序算法

按照通俗的定义， 排序就是按照某种规则，将一组给定的数据对象（记录）排列次序，其主要的目的是提高数据检索的效率，通常数据对象有多个属性域，即由多个数据成员组成，其中一个属性域可以用来区分对象，并作为排序的依据，则该属性域就成为关键字（key），这个数据对象中的关键字的值叫做键值。

进一步明确地定义，排序是将一组数据对象（记录）按照相应的关键字的键值递增或递减的次序重新排列的过程。键值的递增排序叫做升序（又称正序）， 键值的递减排列顺序称为降序（又称逆序）。

本文使用 Python 来实现常见的经典排序算法。

一. 插入排序

直接插入排序

• 将顺序存储的 n 个待排序记录划分为两个区间：一个有序区间，一个无序区间；初始时有序区间为 [R1]，无序区间为 [R2...Rn]，令 i 指向无序区中第一个元素，初始值 i=1。
• 当 i<=n 时重复指向： 将当前无序区中的第一个记录Ri插入到有序区的适当位置，使得有序区变为一个新的有序区。
• 当 i>n 时结束排序。

时间复杂度为O(n^^2), 空间复杂度为O(1)。

def insert_sort(target):
    for i in range(1, len(target)):
        tmp = target[i]
        if tmp < target[i-1]:
            j = i - 1
            while tmp < target[j] and j >= 0:
                target[j+1] = target[j]
                j -= 1
            target[j+1] = tmp
    return target

print(insert_sort([1, -1, -2, -1, -19, 0]))

折半插入排序

从前面的直接插入排序算法中，不难看出每项都进行了如下操作：

1. 从前面的有序字表中找出待插入元素应该被插入的位置。

2. 给插入的位置腾出空间，将带插入的元素复制到表中的插入位置。

注意到该算法中，总是边比较边移动元素，下面将比较和移动操作分离出来，即先用折半查找出元素的待插入位置，然后再统一移动带插入位置之后的所有元素。

因为只减少了比较次数，移动次数并没有减少，所以时间复杂度为O(n^^2), 空间复杂度为O(1)。

def insert_sort(target):
    for i in range(1, len(target)):
        tmp = target[i]
        low, high = 0, i-1
        while low <= high:
            middle = (low + high) // 2
            if tmp < target[middle]:
                high = middle - 1
            else:
                low = middle + 1

        for j in range(i-1, high, -1):
            target[j+1] = target[j]
        target[high+1] = tmp
    return target


print(insert_sort([1, -1, -2, -1, -19, 0]))

希尔排序

希尔排序（ShellPass）也叫缩小增量排序(Diminishing Increment Sort)，它是插入排序的一种，它在时间复杂度上比直接插入排序要好。基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列"基本有序"时，再对全体记录进行一次直接插入排序。

在希尔排序中执行时间依赖于增量序列。好的增量序列的共同特征：最后一个增量必须为1，并且应该尽量避免序列中的值互为倍数。
d = floor(d/2) d = floor(d-1/2) d = floor(d+1/3) d = floor(d-1/3)
当d等于1时，希尔排序和插入排序基本一致。

基本步骤：

• 将整个待排序列以步长为d分为若干子序列，把相隔为d的记录放在同一组。
• 在每个分组类进行直接插入排序。
• 更改d的值，重复上述步骤，直到d的值为1，即所有的记录都放入了一个组中进行插入排序了。

注意：

• watch_j 的意思是保存for循环里面j的值，目的是当这个for循环里面tmp < target[j]全都满足时更新target[watch_j] = tmp
• 注意for else的用法，只有for里面没有break而结束for循环时执行else语句。

时间复杂度为O(n^^1.25), 空间复杂度为O(1)。

def shell_sort(target):
    d = length = len(target)
    while True:
        d = (d + 1) // 3
        if d < 1:
            return target
        for i in range(d, length):
            tmp = target[i]
            if tmp < target[i-d]:
                j = i - d
                while tmp < target[j] and j >= 0:
                    target[j+d] = target[j]
                    j -= d
                target[j+d] = tmp

print(shell_sort([4, 0, -1, 2, 1, -1]))

二. 交换排序

交换排序（Exchange Sort）是一种在排序过程中借助于交换操作来完成排序的方法。交换排序的基本思想时两两比较待排序记录的关键字，如果发现两个关键字逆序，则将两个记录位置互换，重复此过程直到所有关键字有序为止。

冒泡排序

冒泡排序需要两次循环，最外层是控制已经排完序的区间，内层循环控制未排完序区间的比较。

注意exchange遍历没有也可以实现，exchange 的作用是如果某一趟没有交换过数据，那么表示这个序列已经有序了。

时间复杂度为O(n^^2), 空间复杂度为O(1)。

def bubble_sort(target):
    for i in range(len(target)-1, 0, -1):
        exchange = False
        for j in range(i):
            if target[j] > target[j+1]:
                tmp = target[j]
                target[j] = target[j+1]
                target[j+1] = tmp
                exchange = True
        if not exchange:
            break
    return target

print(bubble_sort([4,2,1,-1]))

快速排序

快速排序采用分治法，将问题分解为更小的问题分别求解，基本思想如下：先通过一趟排序，将待排序记录分割成独立的两部分，一中一部分记录的关键字均比另外一部分关键字小，然后可分别对这两部分记录进行排序，已达到整个序列有序的目的。

因为每一次将待排序记录分割为两部分的逻辑一样，所以采用递归的方式。

时间复杂度为O(n*log2*n)，n乘以log 2底n，空间复杂度为O(n)。

def quick_sort(target):

    def _quick_pass(i, j):
        middle_value = target[i]
        while i < j:
            while target[j] > middle_value and i < j:
                j -= 1
            if i < j:
                target[i] = target[j]
                i += 1
                while target[i] <= middle_value and i < j:
                    i += 1
                if i < j:
                    target[j] = target[i]
                    j -= 1
        target[i] = middle_value
        return i

    def _quick_sort_recursive(start, end):
        if start < end:
            middle_index = _quick_pass(start, end)
            _quick_sort_recursive(start, middle_index-1)
            _quick_sort_recursive(middle_index+1, end)

    _quick_sort_recursive(0, len(target)-1)
    return target

print(quick_sort([4,2,1,-1]))

三. 选择排序

选择排序（Selection Sort）的基本思想是：每一趟排序（i=1,1,2,3...,n-1）在 n-i+1 个待排序记录中选出关键字最小的记录，作为有序序列的第i个记录，直到全部排序完毕为止。常用的选择排序有直接选择排序和堆排序。

直接选择排序

直接选择排序（Straight Selection Sort）又称为简单选择排序。基本思想入下：把顺序存储的n个待排序记录看成是由一个有序区和一个无序区，初始状态有序区为空，无序区为（R1,...Rn）。每一趟从无序区中找出最小的元素，将其和无序区的开头交换，这样有序区的元素就增加了一个，无序区的元素就减少了一个了。

时间复杂度为O(n^^2)，空间复杂度为O(1)。

def select_sort(target):
    length = len(target)
    for i in range(length-1):
        watch_i = i
        for j in range(i+1, length):
            if target[j] < target[watch_i]:
                watch_i = j
        if watch_i != i:
            tmp = target[watch_i]
            target[watch_i] = target[i]
            target[i] = tmp
    return target

print(select_sort([4,2,1,-1]))

堆排序

满二叉树： 在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的一个二叉树叫做满二叉树。

完全二叉树：如果对二叉树的节点按照从上至下、从左至右的顺序进行编号，如果编号为 i 的节点与满二叉树中编号为 i 的节点在二叉树中的位置相同，则这颗二叉树称为完全二叉树。

完全二叉树特点

• 叶子节点只能出现在最下层、次下层。
• 最下层的叶子节点集中在树的左部。

堆排序是一种树形选择排序方法，它的特点是在排序过程中，将L[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字大（或最小）的元素。

堆的定义

n 个关键字序列 L[1...n] 称为堆，当且仅当该序列满足：

1. L(i) <= L(2i) 且 L(i) <= L(2i+1)
2. 或者L(i) >= L(2i) 且 L(i) >= L(2i+1)

满足第一种情况的堆称为小根堆，满足第二种情况的称为大根堆

堆排序的基本思想

1. 将整个待排记录分为有序区和无序区，初始时有序区为空，无序区为[L1,L2....Ln]。
2. 构造初始堆。将初始无序区中记录看做一个顺序存放的完全二叉树上的节点，对该完全二叉树按照堆定义进行调整，使得关键字最大的记录成为二叉树的根节点，即L1
3. 每趟排序操作。将根节点记录与无序区的最后一个节点交换，并将无序区的最后一个记录划入有序区内。
4. 堆调整。由于交换后新的根L1可能违反了堆的定义，故应将当前无序区重新调整为堆，使得根节点的关键字最大。
5. 重复3、4步骤，直到无序区为空位置

注意

1. 小根堆和大根堆类似，小根堆得到的是逆序，大根堆得到的是正序。
2. 堆排序和直接选择排序相反，在任何时刻，堆排序的无序区总在有序区之前，且有序区是在无序区的尾部向前逐步扩大至整个序列。

堆调整算法

每趟排序之前是以L1为根的堆，在L1与Ln交换之后，新的无序区中只有L1的值发生了变化，所以除了L1违反了堆的性质外，其余以任何节点为根的子树都是堆。因此需要对当前根节点按照堆性质进行调整，使得调整后得到新的堆。

1. 每趟排序在完成堆顶元素与堆中最后一个元素交换后，将当前根节点的值与左、右子树（若存在）的根节点值进行比较，若当前根节点的值不小于这两个孩子节点的值，则当前根节点未违反堆的定义，无序调整。否则将当前根节点和它的两个孩子中较大者进行交换。
2. 重复上述步骤，直到当前被调整的节点已满足堆的定义，或者孩子节点已经是叶子节点为止。

时间复杂度为O(n*log2*n)，n乘以log 2底n，空间复杂度为O(1)。

def heap_sort(target):

    def _init():
        if not target:
            return target
        # 列表的第0个元素无效，数据从target[1]开始。
        target.insert(0, 0)

    def _heap_rectify(low, high):
        tmp = target[low]
        i = low
        j = 2 * i
        while j <= high:
            if j < high and target[j] < target[j+1]:
                j += 1
            if tmp < target[j]:
                target[i] = target[j]
                i = j
                j = 2 * i
            else:
                break
        target[i] = tmp

    def _heap_build():
        length = len(target) - 1
        for i in range(length // 2, 0, -1):
            _heap_rectify(i, length)

    def _heap_sort():
        length = len(target) - 1
        for i in range(length, 1, -1):
            tmp = target[i]
            target[i] = target[1]
            target[1] = tmp
            _heap_rectify(1, i-1)

    _init()
    _heap_build()
    _heap_sort()
    target.pop(0)
    return target

print(heap_sort([4, 1, 0, -1, 9]))

_heap_rectify 是堆调整函数， _heap_build堆初始化函数，_heap_sort堆排序。列表的第0个元素无效，数据从 target[1] 开始。

四. 归并排序

归并排序是将若干个有序的子序列进行归并，从而合成一个新的有序的序列，其方法是：比较各子序列的第一个记录的关键字，最小的一个就是排序后序列的第一个记录关键字，取出这个关键字，继续比较各子序列当前的第一个记录的关键字，便可以找出排序后的第二个记录，如此下去，知道各子序列均为空为时便得到了最终的排序结果。

二路归并排序

如果同时利用两个有序序列的合并来实现归并排序，这种归并排序称为二路归并排序，二路归并排序是最简单的归并算法。

二路归并排序循环实现

时间复杂度为O(n*log2*n)，n乘以log 2底n，空间复杂度为O(n)。

def merge_sort(target):
    length = len(target)
    target.insert(0, 0)

    def _merge(low, middle, high):
        i, j, k = low, middle+1, 0
        ret = []
        while i <= middle and j <= high:
            if target[i] < target[j]:
                ret.append(target[i])
                i, k = i+1, k+1
            else:
                ret.append(target[j])
                j, k = j+1, k+1
        while i <= middle:
            ret.append(target[i])
            i, k = i+1, k+1
        while j <= high:
            ret.append(target[j])
            j, k = j+1, k+1

        i, k = low, 0
        while i <= high:
            target[i] = ret[k]
            i, k = i+1, k+1
        del ret

    def _merge_pass(sub_len):
        i = 1
        while i+2*sub_len-1 <= length:
            _merge(i, i+sub_len-1, i+2*sub_len-1)
            i = i + 2*sub_len
        if i+sub_len-1 < length:
            _merge(i, i+sub_len-1, length)

    def _merge_sort():
        i = 1
        while i < length:
            _merge_pass(i)
            i = 2 * i

    _merge_sort()
    target.pop(0)
    return target

print(merge_sort([-1, -1, 0, 9, -1]))

二路归并排序递归实现

def merge_sort(target):

    def _merge(low, middle, high):
        i, j, k = low, middle+1, 0
        ret = []
        while i <= middle and j <= high:
            if target[i] < target[j]:
                ret.append(target[i])
                i, k = i+1, k+1
            else:
                ret.append(target[j])
                j, k = j+1, k+1
        while i <= middle:
            ret.append(target[i])
            i, k = i+1, k+1
        while j <= high:
            ret.append(target[j])
            j, k = j+1, k+1

        i, k = low, 0
        while i <= high:
            target[i] = ret[k]
            i, k = i+1, k+1
        del ret

    def _merge_sort(low, high):
        if low < high:
            middle = (low + high) // 2
            _merge_sort(low, middle)
            _merge_sort(middle+1, high)
            _merge(low, middle, high)

    _merge_sort(0, len(target)-1)
    return target

print(merge_sort([-1, -1, 0, 9, -1]))

五. 基数排序

基数排序与前面的排序算法思想有很大不同，前面的排序算法都是以关键字的比较和数据的移动为主，但是基数排序却主要是通过“分配”和“收集”两种操作来实现目的的，是用多对关键字进行排序的思想实现对单个关键字进行排序的方法。

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。

它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较，将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

• 时间复杂度为O(d(n+rd))。 d表示关键字的位数，n表示待排序元素个数，rd表示基数（比如0~9）
• 空间复杂度为O(n+2rd)。n表示待排序元素个数，rd表示基数（比如0~9）

class RadixSort:
    key_size = 5        # 表示排序数字的最大位数
    radix = 10          # 基数为10（0,1,2,3,4,5,6,7,8,9）个
    head = [0] * radix  # 队列的队头
    tail = [0] * radix  # 队列的队尾

    class Node:
        __slots__ = ('value', 'next', 'key')

        def __init__(self, value, next_one=0):
            key_size = RadixSort.key_size
            self.value = value
            self.next = next_one
            self.key = [int(i) for i in str(abs(self.value))[:key_size]]
            while len(self.key) != key_size:
                self.key.insert(0, 0)

        def __str__(self):
            return f'value:{self.value}, next:{self.next}, key:{self.key}'

    @classmethod
    def _distribute(cls, nodes, position):
        head, tail = cls.head, cls.tail
        for j in range(cls.radix):
            head[j] = tail[j] = 0
        p = nodes[0].next
        while p != 0:
            j = nodes[p].key[position]
            if head[j] == 0:
                head[j] = p
            else:
                t = tail[j]
                nodes[t].next = p
            tail[j] = p
            p = nodes[p].next

    @classmethod
    def _collect(cls, nodes):
        head, tail = cls.head, cls.tail
        j = 0
        while head[j] == 0:
            j += 1
        nodes[0].next = head[j]
        t = tail[j]
        while j < cls.radix-1:
            j += 1
            while j < cls.radix-1 and head[j] == 0:
                j += 1
            if head[j] != 0:
                nodes[t].next = head[j]
                t = tail[j]
        nodes[t].next = 0

    @classmethod
    def sort(cls, target):
        length = len(target)
        target.insert(0, 0)
        nodes = []
        for i in range(length+1):
            node = cls.Node(target[i], i+1)
            nodes.append(node)
        nodes[-1].next = 0

        position = cls.key_size - 1
        while position >= 0:
            cls._distribute(nodes, position)
            cls._collect(nodes)
            position -= 1

        ret = []
        current = 0
        while True:
            current = nodes[current].next
            if current == 0:
                break
            node = nodes[current]
            ret.append(node.value)

        return ret


print(RadixSort.sort([544, 3, 19, 324]))