# 导入heapq包
    import heapq
    # 将x压入堆中
    heapq.heappush(heap, x)   
    # 从堆中弹出最小的元素                                     
    heapq.heappop(heap)    
    # 让列表具备堆特征                                  
    heapq.heapify(heap) 
    # 弹出最小的元素，并将x压入堆中                                      
    heapq.heapreplace(heap, x)  
    # 返回iter中n个最大的元素                          
    heapq.nlargest(n, iter) 
    # 返回iter中n个最小的元素                                      
    heapq.nsmallest(n, iter)                                   
    # 从一个list中获取最大的元素
    max_column_data = heapq.nlargest(1, temp_list, key=lambda item: len(item))

    list.sort(cmp=None, key=None, reverse=False)

• cmp -- 可选参数, 如果指定该参数会使用该参数的方法进行排序。
• key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序，一般传入的是一个定义好的函数。
• reverse -- 排序规则，reverse = True 降序， reverse = False 升序（默认）。

• 该方法没有返回值，但是会对列表的对象进行排序。

「435. 无重叠区间」中按照嵌套子列表的第二个元素进行升序排列：

    takesecond = lambda x : x[1]
    intervals.sort(key = takesecond)  # 其中intervals为[[1,2], [2,3], [3,4], [1,3]]的格式

    sorted(iterable, cmp=None, key=None, reverse=False)

• iterable -- 可迭代对象。
• cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
• key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

• 返回重新排序的列表。

• sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
• list 的 sort 方法对列表原地排序，无返回值；内建函数 sorted 方法返回的是一个新的 list，原列表不会发生变化。

• 每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

• 平均情况：O(N²)
• 最好情况：O(N)，数组已经有序
• 最坏情况：O(N²)，数组逆序

• O(1)

• 稳定

• 折半插入排序是对直接插入排序算法的一种改进，由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

折半插入排序算法比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(N²)，与直接插入排序算法相同。

• 平均情况：O(N²)
• 最好情况：O(N)，数组已经有序
• 最坏情况：O(N²)，数组逆序

• O(1)

• 稳定

• 希尔排序又称为“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是把序列按下标的一定增量分组，对每组元素使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，所有元素都被分成一组，算法便终止。

• 平均情况：O()

• O(1)

• 不稳定

• 从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

• 平均情况：O(N²)
• 最好情况：O(N)，数组已经有序
• 最坏情况：O(N²)，数组逆序

• O(1)

• 稳定

• 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 平均情况：O(Nlog₂N)
• 最好情况：O(Nlog₂N)，基准元素选取得当，每次都能均匀的划分序列
• 最坏情况：O(N²)，基准元素恰好是最大或最小元素

• O(log₂N)，递归树的深度

• 不稳定

    # 快速排序递归实现
    def quick_sort(self, nums: List[int], low: int, high: int):
        if low < high:
            pivotpos = self.partition(nums, low, high)
            self.quick_sort(nums, low, pivotpos - 1)
            self.quick_sort(nums, pivotpos + 1, high)
    
    # pivot的优化选取：随机选取
    def partition(self, nums: List[int], low: int, high: int) -> int:
        pos = random.randint(low, high)
        # 将low与pos的元素交换位置，此时可以和普通的快排一样执行划分函数
        nums[low], nums[pos] = nums[pos], nums[low]

        # 普通快排的划分步骤
        pivot = nums[low]
        while low < high:
            while low < high and nums[high] >= pivot:
                high -= 1
            nums[low] = nums[high]
            while low < high and nums[low] <= pivot:
                low += 1
            nums[high] = nums[low]
        nums[low] = pivot
        return low

快排优化思路：https://blog.csdn.net/insistGoGo/article/details/7785038

• 从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

• 平均情况：O(N²)
• 最好情况：O(N²)
• 最坏情况：O(N²)

• O(1)

• 不稳定

• 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

• 平均情况：O(Nlog₂N)
• 最好情况：O(Nlog₂N)
• 最坏情况：O(Nlog₂N)

• O(1)

• 不稳定

• 把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

• 平均情况：O(Nlog₂N)
• 最好情况：O(Nlog₂N)
• 最坏情况：O(Nlog₂N)

• O(N)

• 稳定