关于python:一篇夯实一个知识点系列－－python实现十大排序算法

写在后面

排序是查找是算法中最重要的两个概念，咱们大多数状况下都在进行查找和排序。科学家们穷尽致力，想使得排序和查找可能更加疾速。本篇文章用 Python 实现十大排序算法。

干货儿

排序算法从不同维度能够分为好多类别，从其排序思维 (排序思维个别决定了其工夫复杂度的量级) 来看，次要能够分为四类：

• 双层循环比拟排序：平方级排序
• 分治策略比拟排序：对数级排序
• 另辟蹊径的非比拟形式排序：线性级排序
• 笑死人不偿命的其它排序：有着天马行空的工夫复杂度，难以描述。

平方级排序

• 冒泡排序

  1. 从数组的第一个元素开始，比拟以后元素和下一个元素，如果以后元素大于下一个元素，替换两元素地位。
  2. 接着从第二个元素开始，反复第一步，直到以后元素为最初一个元素。此时最初一个元素为最大元素。未排序数组为除最初一个元素之外的其它元素。
  3. 对未排序数组一直反复以上步骤，直到未排序数组为空。

  def bubble_sort(arr):
      length = len(arr)
      for i in range(length):
          for j in range(length-i-1):
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]
      return arr

• 抉择排序

  1. 选取数组中的最小元素，和数组中的第一个元素替换地位
  2. 选取数组中除第一个元素外残余元素的最小元素，和数组中的第二个元素替换地位。
  3. 一直反复以上步骤，直到以后选取的元素为数组中最初一个元素。

  def select_sort(arr):
      length = len(arr)
      for i in range(length):
          min_ix = i
          for j in range(i, length):
              if arr[j] < arr[min_ix]:
                  min_ix = j
          arr[min_ix], arr[i] = arr[i], arr[min_ix]
      return arr

• 插入排序

  1. 从数组的第一个元素开始，一直比拟以后元素和前一个元素。如果以后元素比前一个元素小，那么就将以后元素插入到前一个元素的后面(即两者替换地位)
  2. 从第二个元素开始，一直反复以上步骤，直到所有元素全副经验上述步骤。

  def insert_sort(arr):
      length = len(arr)
      for i in range(length):
          for j in range(i, 0, -1):
              if arr[j] < arr[j-1]:
                  arr[j], arr[j-1] = arr[j-1], arr[j]
      return arr

对数级排序

• 希尔排序

  1. 抉择一个增量值 k，别离将数组中索引以 k 为距离的元素放在同一个数组中。
  2. 将增量值放大为原增量值的 1 /2，而后反复步骤 1。
  3. 直到增量值为 1，应用插入排序对曾经局部有序的数组进行排序。

  def shell_sort(arr):
      n = len(arr)
      gap = int(n/2)
      while gap > 0: 
          for i in range(gap,n): 
              temp = arr[i] 
              j = i 
              while  j >= gap and arr[j-gap] >temp: 
                  arr[j] = arr[j-gap] 
                  j -= gap 
              arr[j] = temp 
          gap = int(gap/2)
      return arr

• 归并排序

  1. 以数组两头元素为界，将数组分为等长的两个数组(可能不等长，和数组长度的奇偶性无关)。
  2. 对所有数组执行步骤 1
  3. 一直反复以上步骤，直到将数组宰割为多个蕴含单个元素的数组。
  4. 将以上数组两两合并，并排序，此时为多个蕴含有序的两个元素的数组(可能蕴含单个元素，跟数组长度的奇偶性无关)。
  5. 反复步骤 4，直到将所有数组合并为一个数组

  def merge(left, right):
      i = j = 0
      res = []
      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              res.append(left[i])
              i += 1
          else:
              res.append(right[j])
              j += 1
      if i == len(left):
          res.extend(right[j:])
      else:
          res.extend(left[i:])
      return res
  
  def merge_sort(arr):
      if len(arr) <= 1:
          return arr
      length = len(arr)
      i = int(length / 2)
      left = merge_sort(arr[:i])
      right = merge_sort(arr[i:])
      return merge(left, right)

• 疾速排序

  1. 筛选一个元素为基准
  2. 比基准大的元素作为一个数组，比基准小或者等于基准的元素作为一个数组。
  3. 对新宰割的数组，一直反复以上步骤，直到宰割后的数组只含有 1 个或者 0 个元素
  4. 递归地合并以上数组为有序数组，合并形式为：[小于等于基准的元素]+[基准]+[大于基准的元素]

  def fast_sort(arr):
      if len(arr) <= 1:
          return arr
      pivot = arr.pop()
      left = [i for i in arr if i <= pivot]
      right = [i for i in arr if i > pivot]
      return fast_sort(left) + [pivot] + fast_sort(right)

  以上算法须要额定的空间，如果咱们将小于等于基准的元素一直置于基准元素之前，大于基准的元素置于基准元素之后，那么就能够实现不须要额定空间的就地排序。

  def fast_sort_on_extra_spacing(arr):
      l = 0
      h = len(arr)-1
  
      def partition(arr, l, h):
          pivot = arr[h]
          for i in range(l, h):
              if arr[i] <= pivot:
                  arr[l], arr[i] = arr[i], arr[l]
                  l += 1
          arr[h], arr[l] = arr[l], arr[h]
          return l
  
      def fast_sort(arr, l, h):
          if l < h:
              pivot = partition(arr, l, h)
              fast_sort(arr, l, pivot-1)
              fast_sort(arr, pivot+1, h)
          return arr
      return fast_sort(arr, l, h)

• 堆排序

  1. 先看待排序数组结构大根堆
  2. 将大根堆第一个元素和最初一个元素替换地位。此时最初一个元素为最大元素，待排序数组为除最初一个元素之外的所有元素。
  3. 看待排序数组一直反复以上步骤，直到待排序数组中只有一个元素。

  def heapify(arr, n, i):
      # build a max root heap
      max_ix = i
      left_i = 2 * i + 1
      right_i = 2 * i + 2
  
      if left_i < n and arr[max_ix] < arr[left_i]:
          max_ix = left_i
      if right_i < n and arr[max_ix] < arr[right_i]:
          max_ix = right_i
      if max_ix != i:
          arr[max_ix], arr[i] = arr[i], arr[max_ix] 
          heapify(arr, n, max_ix)
  
  def heap_sort(arr):
      for i in range(n-1, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
          heapify(arr, i, 0)
      return arr

线性级排序

此排序办法只实用于数组元素全副为整数的情景。

• 计数排序

  1. 找出待排序数组中最大的元素，结构一个长度为此元素值的计数数组。
  2. 遍历待排序数组元素，以以后元素为索引，将计数数组中的对应值加 1.
  3. 此时计数数组中的索引为待排序数组中的元素，值为呈现的次数。将计数数组中所有值非 0 的元素索引依据其呈现次数串联起来。

  def count_sort(arr):
      min_ix, max_ix = min(arr), max(arr)
      bucket = [0 for _ in range(max_ix+1)]
      for i in arr:
          bucket[i] += 1
      return sum([[i] * bucket[i] for i in range(len(bucket)) if bucket[i] != 0], [])

• 桶排序

  1. 设置固定数量的桶(这是个技术活儿).
  2. 将待排序数组中的元素放入对应的桶中(对应关系也是个技术活儿，上面的例子中采纳整除)
  3. 将非空桶中的元素串联起来。

  def bucket_sort(arr):
      min_ix, max_ix = min(arr), max(arr)
      bucket_range = (max_ix - min_ix) / len(arr)
      # +1 avoid for that max_ix - min_ix will raise a IndexError
      temp_bucket = [[] for i in range(len(arr) + 1)]
      for i in arr:
          temp_bucket[int((i-min_ix)//bucket_range)].append(i)
      return sum(temp_bucket, [])

• 基数排序

  1. 找出待排序数组中最大元素的位数。将所有元素补足此位数，补足形式为后面补 0。
  2. 从最低位到最高位，进行多轮数组排序。

  def radix_sort(arr):
      max_value = max(arr)
      num_digits = len(str(max_value))
      for i in range(num_digits):
          bucket = [[] for _ in range(10)]
          for j in arr:
              bucket[j//(10**i)%10].append(j)
          arr = [j for i in bucket for j in i]
      return arr

笑死人不偿命排序

• 睡排序

  让多个过程 (线程) 别离睡眠待排序数组中的元素时长，先睡醒的过程(线程)，对应元素追加到后果数组中。

• 猴子排序

  不停随机排序，而后查看是否元素全副有序。如果你是欧皇，那么你能够尝试用这个排序算法，很可能一次搞定。

排序算法复杂度、稳定性及通用性总结

写在最初

排序算法是算法学习中的外围。把握排序算法及其思维是学习其它算法的根底。心愿大家能够熟练掌握。欢送关注集体博客: 药少敏的博客。