一、基本排序

1.1 选择排序

• 原理
  从未排序的元素中选择最小（最大）值放到已排序的元素后面。
• 实现

  def select_sort(items = [],
              reverse = False):
      '''
      获取一个存储value的列表，经选择排序后返回新的列表
      默认由小到大排序,reverse为True时由大到小排序
      '''
      # 避免影响原始列表
      items_copy = items.copy()
      # 避免重复计算
      length = len(items_copy)
      for i in range(length-1):
          min_index = i
          for j in range(i+1, length):
              if items_copy[j] < items_copy[min_index]:
                  min_index = j
          items_copy[i], items_copy[min_index] = items_copy[min_index], items_copy[i]
      if reverse:
          return list(reversed(items_copy))
      return items_copy

1.2 冒泡排序

• 原理
  比较相邻元素，较小（较大）者往前移动
• 实现

  def bubble_sort(items = [],
             reverse = False):
      '''
      获取一个存储value的列表，经冒泡排序后返回新的列表
      默认由小到大排序,reverse为True时由大到小排序
      '''
      # 避免影响原始列表
      items_copy = items.copy()
      # 避免重复计算
      length = len(items_copy)
      for i in range(length-1):
          for j in range(length-1-i):
              if items_copy[j] > items_copy[j+1]:
                  items_copy[j], items_copy[j+1] = items_copy[j+1], items_copy[j]
      if reverse:
          return list(reversed(items_copy))
      return items_copy

1.3 插入排序

• 原理
  以第一个元素为插入基准，后续元素不断往前插入，若较小（较大），则排在基准元素前列。可参考摸扑克牌时整理手牌的过程。
• 实现

  def insert_sort(items = [],
             reverse = False):
      '''
      获取一个存储value的列表，经插入排序后返回新的列表
      默认由小到大排序,reverse为True时由大到小排序
      '''
      # 避免影响原始列表
      items_copy = items.copy()
      # 避免重复计算
      length = len(items_copy)
      for i in range(1,length):
          temp = items_copy[i]
          # 待插入下标
          insert_index = i
          for j in range(i-1,-1,-1):
              # 与已插入数据比较，从后向前
              if items_copy[j] > temp:
                  # 大的数后移空出位置
                  items_copy[j+1] = items_copy[j]
                  insert_index = j
              else:
                  break
          items_copy[insert_index] = temp
      if reverse:
          return list(reversed(items_copy))
      return items_copy

二、高级排序

高级排序主要是复杂度较低的常见排序

2.1 归并排序

• 原理
  归并排序主要有两个步骤分治与合并，分治即将长列表不断均分为短列表，对每个短列表进行排序，合并即将这些分别排序后的列表合并成排序后的长列表。
• 实现

  def merge_sort(items = [],
            reverse = False):
      '''
      拆分列表进行归并
      '''
      length = len(items)
      if length < 2:
          return items[:]
      mid = length // 2
      left_part = merge_sort(items[:mid])
      right_part = merge_sort(items[mid:])
      if reverse:
          return list(reversed(merge(left_part,right_part)))
      return merge(left_part,right_part)

  def merge(left_part, right_part):
      '''
      将两个列表合并成一个
      '''
      result_list = []
      while left_part and right_part:
          if left_part[0] <= right_part[0]:
              result_list.append(left_part.pop(0))
          else:
              result_list.append(right_part.pop(0))
      # 将剩余数据添加到结果中
      result_list.extend(left_part)
      result_list.extend(right_part)
      return result_list

2.2 快速排序

• 原理
  快排基于一个中值和两个指针，选定中值后将大于该中值的移到右边，小于该中值的移到左边。
• 实现

  def quick_sort(items,
            reverse = False):
      '''
      快速排序
      '''
      length = len(items)
      if length <= 1:
          return items
      else:
          mid_item = items[0]
          right_items = [item for item in items[1:] if item > mid_item]
          left_items = [item for item in items[1:] if item <= mid_item]
          if reverse:
              return list(reversed(quick_sort(left_items) + [mid_item] + quick_sort(right_items)))
          return quick_sort(left_items) + [mid_item] + quick_sort(right_items)

分享到：

赞(1)