冒泡、插入、选择

冒泡（Bubble Sort）

冒泡排序的思想就是两两比较，不断的最大/最小的数放到最后面。

• Python

  def bubble(lst):
      for i in range(len(lst)):
          flag = False
          for j in range(len(lst)-i-1):
              if lst[j] > lst[j+1]:
                  lst[j], lst[j+1] = lst[j+1], lst[j]
                  flag = True
          if not flag:
              break
      return lst

1. 冒泡排序是原地排序算法， 空间复杂度是O(1)。
2. 冒泡排序是稳定的排序算法。
3. 冒泡排序的最好时间复杂度是O(n)，最坏是O( n^2 )，平均是O( n^2 )。

插入排序 （Insertion Sort）

插入排序的思想是将数据分为已排序区和未排序区，然后不断的从未排序区中取出一个元素有序的插入到已排序区中。

• Python

  def insert_sort(lst):
      for i in range(1, len(lst)):
          value = lst[i]
          for j in range(i-1, -2, -1):
              if lst[j] > value:
                  lst[j+1] = lst[j]
              else:
                  lst[j] = value
                  break
      return lst

  def insert_sort(lst):
      for i in range(1, len(lst)):
          key = lst[i]
          j = i
          while j > 0 and lst[j-1] > key:
              lst[j] = lst[j-1]
              j = j-1
          lst[j] = key
      return lst

1. 插入排序是原地排序算法，空间复杂度是O(1)
2. 插入排序是稳定的排序算法
3. 插入排序的最好时间复杂度是O(n)， 最坏是O(n^2)， 平均是O(n^2)。

选择排序（Selection Sort）

选择排序的思想与插入排序类似，也是将数据分为已排序区和未排序区，然后不断的从未排序区中选择出最小/最大的放到已排序区的最后面。

• Python

  def select_sort(lst):
      for i in range(len(lst)):
          for j in range(i+1, len(lst)):
              if lst[j] < lst[i]:
                  lst[j], lst[i] = lst[i], lst[j]
      return lst

1. 选择排序是原地排序算法，空间复杂度是O(1)
2. 选择排序是不稳定稳定的排序算法
3. 选择排序的最好时间复杂度是O(n^2)，最坏是O(n^2), 平均是O(n^2)

冒泡、插入、选择

原文：https://www.cnblogs.com/leisurelylicht/p/11-mao-pao-cha-ru-xuan-ze.html