冒泡排序

• 特点
  时间复杂度 O(n^2 )，非常慢。

• 算法
  外层指针，循环整个列表。
    内层指针，循环整个列表 - 外层循环次数
      遍历每个元素和该元素的下一个元素，如果顺序不一致，则调换两个元素。

• 代码

def bubble_sort(arr):
    """
    poping the greatest value to the right
    """
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

插入排序

• 特点
  最坏情况时间复杂度 O(n^2 )，非常慢。
  对于近乎有序的列表，速度很快。

• 算法
  外层指针，循环整个列表一次。每次指向一个元素。
    内层指针，对于每个外层指针指到的元素，从该角标处开始，倒序循环，
      判断内层指针指到的元素与外层指针指到的元素的大小关系。
      如果和排序要求不一致，则将内层指针指到的元素后移一位。
      如果和排序要求一致，则停止该内层指针的循环。
      如果内层指针回到列表起始处，也停止该内层指针的循环。
      停止循环后，在内层指针的位置插入外层指针指到的元素。

• 代码

def insertion_sort(arr）:
    """
    shift all greater values to the right
    """
    for i in range(1, len(arr)):
        cur = arr[i]
        prev = i - 1

        while prev >= 0 and arr[prev] > cur:
            arr[prev + 1] = arr[prev]
            prev -= 1
        arr[prev + 1] = cur
    return arr

插入法从小到大排序，当外层指针指到数字1时的内层循环

选择排序

• 特点
  时间复杂度 O(n^2 )，非常慢。
• 算法
  外层指针，循环整个列表
    内层指针，循环整个列表 - 外层循环次数
      每次循环，取出循环范围内的最大或最小值，放到一边。
• 代码

def selection_sort(arr):
    """
    exchange the greatest value and the right last value
    """
    for i in range(0, len(arr)):
        max_index = 0

        for j in range(1, len(arr) - i):
            if arr[j] > arr[max_index]:
                max_index = j

        arr[len(arr) - 1 - i], arr[max_index] = arr[max_index], arr[len(arr) - 1 - i]
    return arr

希尔排序

• 特点
  插入排序的改进版。
  时间复杂度介于O(n(logn))与O(n^2 )之间。适用于中等规模排序。

• 算法
  不对整个列表进行外层循环，而是拆成若干组各自进行插入排序。
  拆成组的个数：len(li) / 2 → len(li) / 4 → len(li) / 8 → ... → 2 → 1

  
  
  分成 8 / 2 = 4 组
  
  
  分成 8 / 4 = 2 组
  
  
  分成 1 组

归并排序

• 特点
  时间复杂度为O(nlogn)，速度快，稳定。适用于数据量大的排序。

• 算法
  基于分治法的排序。
  基础是将两个有序的列表，合并为一个有序的列表。
  为两个有序列表各定义一个指针。定义一个新的空列表。
  两个指针指向的元素进行比较。较小的元素放入空列表，同时指向该较小元素的指针后移一位。
  当其中一个列表的元素遍历完成后，将另一个列表剩下的元素放入空列表。
  空列表是两个就是排好序的合并列表。

  
  
  合并有序列表A和B，结果为列表C

递归由下至上进行归并排序