排序算法总结（基于Python）

排序算法总结（基于Python）

文章目录

• 排序算法总结（基于Python）
• • 比较排序
  • • 冒泡排序
    • 梳排序
    • 堆排序
    • 归并排序
    • 快速排序
    • 内省排序
    • Timesort
    • 非比较排序
    • • 桶排序
      • 基���排序

        比较排序

        (基于比较的排序)给定一个包含 n n n个对象的待排序序列 a 1 , a 2 , . . . , a n {a_1},{a_2},...,{a_n} a1​,a2​,...,an​。假如已知如何比较任意两个对象的大小关系，以及如何对这一序列排序。对于自定义对象，比较规则应当满足两个性质：传递性和全序性。

        冒泡排序

        冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

        （）

        特点：调整相邻两个对象的位置，每进行一次内循环，将最大值调整到最后。

        时间复杂度： O ( n 2 ) {\rm{O}}\left( {{{\rm{n}}^2}} \right) O(n2)

        def bubble_sort(arr):    n = len(arr)    # 遍历所有数组元素    for i in range(n):        for j in range(0, n - i - 1):            # 比较大小            if arr[j] > arr[j + 1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]

        梳排序

        梳排序是改良自冒泡排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成冒泡排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响冒泡排序的效能。

        （）

        冒泡排序总是比较相邻的值。所以一次交换中只能删除一个逆序计数。而梳式排序通过使用大于1的间隔来改进冒泡排序。间隔从一个较大的值开始，并在每次迭代中缩小1.3倍，直到达到值1。因此，梳式排序在一次交换中删除了多个逆序计数，比冒泡排序性能上更好。

        收缩系数的设定影响着梳排序的效率。根据经验，收缩系数是1.3 (通过在超过20万个随机列表上测试梳排序)。

        虽然平均情况下，它比冒泡排序性能更好，但在最坏的情况下仍然是 O ( n 2 ) {\rm{O}}\left( {{{\rm{n}}^2}} \right) O(n2)。

        def comb_sort(arr):    the_len = len(arr)    if the_len = 1:            for j in range(the_len):                if i + j >= the_len:                    i = int(i / 1.3)                    break                else:                    if arr[j] >= arr[j + i]:                        arr[j], arr[j + i] = arr[j + i], arr[j]        return arr

        堆排序

        堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法。堆的结构是一棵完全二叉树的结构，并且满足堆积的性质：每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。

        堆排序先按从上到下、从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树，然后对完全二叉树进行调整，使其满足堆积的性质：每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。构建出堆后，将堆顶与堆尾进行交换，然后将堆尾从堆中取出来，取出来的数据就是最大(或最小)的数据。重复构建堆并将堆顶和堆尾进行交换，取出堆尾的数据，直到堆中的数据全部被取出，列表排序完成。总的时间复杂度： O ( n + k log ⁡ n ) {\rm{O}}\left( {n + k\log n} \right) O(n+klogn)

        堆结构分为大顶堆和小顶堆：

        • 大顶堆：每个节点(叶节点除外)的值都大于等于其子节点的值，根节点的值是所有节点中最大的，所以叫大顶堆，在堆排序算法中用于升序排列。

          -小顶堆：每个节点(叶节点除外)的值都小于等于其子节点的值，根节点的值是所有节点中最小的，所以叫小顶堆，在堆排序算法中用于降序排列。

          堆排序的原理如下：

          1. 将待排序列表中的数据按从上到下、从左到右的顺序构造成一棵完全二叉树。
          2. 将完全二叉树中每个节点(叶节点除外)的值与其子节点(子节点有一个或两个)中较大的值进行比较，如果节点的值小于子节点的值，则交换他们的位置(大顶堆，小顶堆反之)。
          3. 将节点与子节点进行交换后，要继续比较子节点与孙节点的值，直到不需要交换或子节点是叶节点时停止。比较完所有的非叶节点后，即可构建出堆结构。
          4. 将数据构造成堆结构后，将堆顶与堆尾交换，然后将堆尾从堆中取出来，添加到已排序序列中，完成一轮堆排序，堆中的数据个数减1。
          5. 重复步骤2,3,4，直到堆中的数据全部被取出，列表排序完成。

          def heap_sort(array):    first = len(array) // 2 - 1    for start in range(first, -1, -1):        # 从下到上，从右到左对每个非叶节点进行调整，循环构建成大顶堆        big_heap(array, start, len(array) - 1)    for end in range(len(array) - 1, 0, -1):        # 交换堆顶和堆尾的数据        array[0], array[end] = array[end], array[0]        # 重新调整完全二叉树，构造成大顶堆        big_heap(array, 0, end - 1)    return arraydef big_heap(array, start, end):    root = start    # 左孩子的索引    child = root * 2 + 1    while child