二、排序：时间复杂度O(n*logn)

2.1 快速排序

class QuickSort:
    """
    快速排序
    时间复杂度：最坏 O(n*n)、平均 O(n*logn)、最优 O(n*logn)
    空间复杂度：最坏 O(n)、平均 O(logn)
    简介：
        1 找到列表最左边的元素，将其归位，归位后左边元素都比这个元素小，右边元素都比这个元素大
        2 归位的元素将列表分为左右两部分，这两部分又可以看成两个新列表，再对这两个新列表递归执行步骤一，直到不能再分
    补充：
        避免最坏时间复杂度O(n*n)：
            当列表为有序的情况时，要归位n-1次，效率很低；
            可以在递归时，先将首个元素随机和列表中任意元素替换，再对替换后的首位元素归位
    """

    @staticmethod
    def partition(li, left, right):
        """
        在 li[left, right] 中，对left下标元素进行归位
        :param li: 无序列表
        :param left: 左下标
        :param right: 右下标
        :return: 归位后的下标
        """
        curr = li[left]
        while left < right:
            while left < right and li[right] >= curr:  # 从右侧找到比curr小的
                right -= 1
            li[left] = li[right]  # 换位
            while left < right and li[left] <= curr:  # 从左侧找到比curr大的
                left += 1
            li[right] = li[left]  # 换位
        li[left] = curr  # 原值归位
        return left

    def _sort(self, li, left, right):
        """
        递归调用归位方法，以实现排序
        :param li: 无序列表
        :param left: 左下标
        :param right: 右下标
        :return:
        """
        if left < right:
            # 避免最坏时间复杂度
            rand = random.randint(left, right)
            li[left], li[rand] = li[rand], li[left]

            # 归位
            mid = self.partition(li, left, right)

            # 对左右两个新列表递归执行以上操作
            self._sort(li, left, mid - 1)
            self._sort(li, mid + 1, right)

    def sort(self, li):
        """
        快速排序
        :param li:
        :return:
        """
        self._sort(li, 0, len(li) - 1)
        return li

2.2 堆排序

class HeapSort:
    """
    堆排序
    时间复杂度：最坏 O(n*logn)、平均 O(n*logn)、最优 O(n*logn)
    空间复杂度：O(1)
    简介：
        堆结构：一种特殊的完全二叉树结构
            大根堆：一个完全二叉树，满足任意节点都比其子节点大
            小根堆：一个完全二叉树，满足任意节点都比其子节点小
        向下调整特性：
            一个非堆结构的完全二叉树，当根结点的左右子树都是堆结构时，可以通过一次向下调整，将其变换成一个堆结构
        构建堆：
            1 找到最后一个非叶子节点，利用向下调整特性，将其还原成堆结构
            2 继续找到上一个非叶子节点，利用向下调整特性，将其还原成堆结构
            3 重复步骤2，直到找到最后一个非叶子节点，即跟节点为止，此时构建成堆结构
        顺序取堆内的元素：
            1 拿出堆顶元素
            2 堆尾元素放到堆顶
            3 利用向下调整特性，将其还原成一个新的堆
            4 重复步骤1，直到数据全部取出
    """

    @staticmethod
    def sift(li, low, high):
        """
        向下调整实现
        :param li: 一个非堆结构的完全二叉树，其根结点的左右子树都是堆结构
        :param low: 堆的根节点位置
        :param high: 堆的最后一个元素的位置
        :return:
        """
        i = low  # i开始指向根节点
        j = 2 * i + 1  # j开始指向i的左子节点
        tmp = li[low]  # 把堆顶元素存起来
        while j <= high:  # 只要j位置有元素
            if j + 1 <= high and li[j + 1] > li[j]:  # 如果i有右子节点，且比左子节点大
                j = j + 1  # j指向i的右子节点
            if li[j] > tmp:  # 如果tmp不满足放在当前位置的条件，往下再走一层
                li[i] = li[j]
                i = j
                j = 2 * i + 1
            else:  # tmp满足放在当前位置的条件，把tmp放到i的位置上
                li[i] = tmp
                break
        else:  # tmp只能放在叶子节点上
            li[i] = tmp

    def sort(self, li):
        """
        堆排序
        :param li:
        :return:
        """
        n = len(li)
        for i in range((n - 2) // 2, -1, -1):  # 构建堆，i表示所有非叶子节点的下标
            self.sift(li, i, n - 1)
        for i in range(n - 1, -1, -1):  # i 指向当前堆的最后一个元素
            li[0], li[i] = li[i], li[0]  # 将堆顶元素和堆尾元素交换
            self.sift(li, 0, i - 1)  # 利用向下调整特性将其还原成长度减1的新堆结构
        return li

2.3 归并排序

class MergeSort:
    """
    归并排序
    时间复杂度：最坏 O(n*logn)、平均 O(n*logn)、最优 O(n*logn)
    空间复杂度：O(n)
    简介：
        1 递归将列表越分越小，直到分成一个元素，一个即有序
        2 递归将两个有序列表归并，列表越来越大
    缺点：需要额外内存开销
    """

    @staticmethod
    def merge(li, low, mid, high):
        """
        将两段有序列表归并：列表左段[low, mid]，列表右段[mid+1, high]
        :param li:
        :param low:
        :param mid:
        :param high:
        :return:
        """
        curr_list = []
        left = low
        right = mid + 1
        while left <= mid and right <= high:  # 归并结束条件
            if li[left] < li[right]:  # 左右逐个比较，小的存到临时列表
                curr_list.append(li[left])
                left += 1
            else:
                curr_list.append(li[right])
                right += 1
        while left <= mid:  # 归并结束后，左边剩余
            curr_list.append(li[left])
            left += 1
        while right <= high:  # 归并结束后，右边剩余
            curr_list.append(li[right])
            right += 1
        li[low:high + 1] = curr_list

    def _sort(self, li, low, high):
        """
        递归将列表越分越小，再递归调用归并，最终实现排序
        :param li:
        :param low:
        :param high:
        :return:
        """
        if low < high:
            # 递归将列表越分越小，直到一个元素
            mid = (low + high) // 2
            self._sort(li, low, mid)
            self._sort(li, mid + 1, high)

            # 递归将两个有序列表归并，列表越来越大
            self.merge(li, low, mid, high)

    def sort(self, li):
        """
        归并排序
        :param li:
        :return:
        """
        self._sort(li, 0, len(li) - 1)
        return li