排序算法 - 图2

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    2. 动图演示

    排序算法 - 图3

    3. Python 代码实现

    1. def bubbleSort(arr):
    2.  for i in range(len(arr)-1):
    3.      # 判断是否为最优情况，最终的count如果等于0，就直接return
    4.      count = 0
    5.      for j in range(0, len(arr)-1-i):
    6.          if arr[j] > arr[j+1]:
    7.             arr[j], arr[j + 1] = arr[j + 1], arr[j]
    8.             count += 1
    9.      if count == 0:
    10.          return arr

    4. 时间复杂度

  • 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
  • 最坏时间复杂度：O(n2)
  • 稳定性：稳定

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

    2. 动图演示

    排序算法 - 图4

    3. Python 代码实现

    1. def selectionSort(arr):
    2.  # 需要进行n-1次选择操作
    3.  for i in range(len(arr) - 1):
    4.      # 记录最小数的索引
    5.      minIndex = i
    6.      # 从i+1位置到末尾选择出最小数据
    7.      for j in range(i + 1, len(arr)):
    8.          if arr[j] < arr[minIndex]:
    9.              minIndex = j
    10.      # 如果数组中出现重复数字，i不等于最小数时，将i和最小数进行交换
    11.      if i != minIndex:
    12.          arr[i], arr[minIndex] = arr[minIndex], arr[i]
    13.  return arr

    4. 时间复杂度

  • 最优时间复杂度：O(n2)
  • 最坏时间复杂度：O(n2)
  • 稳定性：不稳定（考虑升序每次选择最大的情况）

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

    2. 动图演示

    image.gif排序算法 - 图6

    3. Python 代码实现

    1. def insertionSort(arr):
    2.  # i = 1 ~ n
    3.  for i in range(1, len(arr)):
    4.      j = i
    5.      while j > 0:
    6.          if arr[j] < arr[j-1]:
    7.              arr[j], arr[j-1] = arr[j-1], arr[j]
    8.              j -= 1
    9.          else:
    10.              break
    11.  return arr

    4. 时间复杂度

  • 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
  • 最坏时间复杂度：O(n2)
  • 稳定性：稳定

希尔排序

也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法，区别就是多了步长。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序

1. 算法步骤（新增步长概念gap）

  1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

排序算法 - 图7

2. 动图演示

排序算法 - 图8

3. Python 代码实现

  1. def shell_sort(alist):
  2.     n = len(alist)
  3.     # 初始步长
  4.     gap = n // 2
  5.     # gap变换到0之前，插入算法执行的次数
  6.     while gap > 0:
  7.         # 与普通插入算法的区别就是gap步长，插入按步长进行插入排序
  8.         for i in range(gap, n):
  9.             j = i
  10.             # 插入排序的方法
  11.             while j > 0:
  12.                 if alist[j-gap] > alist[j]:
  13.                     alist[j-gap], alist[j] = alist[j], alist[j-gap]
  14.                     j -= gap
  15.                 else:
  16.                     break
  17.         # 缩短gap步长
  18.         gap = gap // 2
  19.     return alist

4. 时间复杂度

  • 最优时间复杂度：根据步长序列的不同而不同
  • 最坏时间复杂度：O(n2)
  • 稳定想：不稳定

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。递归太深容易造成内存溢出，所以不如快速排序流行。

1. 算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

    2. 动图演示

    image.gif排序算法 - 图10

    3. Python 代码实现

    1. def merge_sort(alist):
    2.  """归并排序"""
    3.  n = len(alist)
    4.  if n <= 1:
    5.      return alist
    6.  mid = n//2
    8.  # left采用递归方法归并排序后形成的有序的新列表
    9.  left_li = merge_sort(alist[:mid])
    11.  # right采用递归方法归并排序后形成的有序的新列表
    12.  right_li = merge_sort(alist[mid:])
    14.  # 将两个有序的序列合并为一个新的整体
    15.  left_pointer, right_pointer = 0, 0
    16.  result = []
    17.  # 然后对新的整体内部排序
    18.  while left_pointer < len(left_li) and right_pointer < len(right_li):
    19.      if left_li[left_pointer] < right_li[right_pointer]:
    20.          result.append(left_li[left_pointer])
    21.          left_pointer += 1
    22.      else:
    23.          result.append(right_li[right_pointer])
    24.          right_pointer += 1
    26.  result += left_li[left_pointer:]
    27.  result += right_li[right_pointer:]
    28.  return result

    4. 时间复杂度

  • 最优时间复杂度：O(nlogn)
  • 最坏时间复杂度：O(nlogn)
  • 稳定性：稳定

快速排序

在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

1. 算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 遍历剩下的数组，把所有比基准元素小的放在基准元素左边，把所有比基准元素大的放在基准元素右边（相同的数可以到任一边）。
  3. 递归的把左边的子序列和右边的子序列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
排序算法 - 图11

2. 动图演示

排序算法 - 图12

3. Python 代码实现

  1. def quick_sort(alist):
  2.     """快速排序"""
  4.     # 递归的退出条件
  5.     if left >= right:
  6.         return
  8.     # cur为序列左边的由左向右移动的游标
  9.     cur = left
  11.     # pre为序列右边的由右向左移动的游标
  12.     pre = right
  14.     # 设定起始元素为要寻找位置的基准元素
  15.     mid = alist[left]
  17.     while cur < pre:
  18.         # 如果cur与pre未重合，pre指向的元素不比基准元素小，则pre向左移动
  19.         while cur < pre and alist[pre] >= mid:
  20.             pre -= 1
  21.         # 将pre指向的元素放到cur的位置上
  22.         alist[cur] = alist[pre]
  24.         # 如果cur与pre未重合，cur指向的元素比基准元素小，则cur向右移动
  25.         while cur < pre and alist[cur] < mid:
  26.             cur += 1
  27.         # 将cur指向的元素放到pre的位置上
  28.         alist[pre] = alist[cur]
  30.     # 退出循环后，cur与pre重合，此时所指位置为基准元素的正确位置，将基准元素放到该位置
  31.     alist[cur] = mid
  33.     # 使用递归的方法对基准元素左边的子序列进行快速排序
  34.     quick_sort(alist, left, cur-1)
  36.     # 使用递归的方法对基准元素右边的子序列进行快速排序
  37.     quick_sort(alist, cur+1, right)
  39.     return alist
  42. def quick_sort(arr):
  43.     '''模拟栈操作实现非递归的快速排序'''
  44.     if len(arr) < 2:
  45.         return arr
  46.     stack = []
  47.     stack.append(len(arr)-1)
  48.     stack.append(0)
  49.     while stack:
  50.         l = stack.pop()
  51.         r = stack.pop()
  52.         index = partition(arr, l, r)
  53.         if l < index - 1:
  54.             stack.append(index - 1)
  55.             stack.append(l)
  56.         if r > index + 1:
  57.             stack.append(r)
  58.             stack.append(index + 1)
  60. def partition(arr, start, end):
  61.     # 分区操作，返回基准线下标
  62.     pivot = arr[start]
  63.     while start < end:
  64.         while start < end and arr[end] >= pivot:
  65.             end -= 1
  66.         arr[start] = arr[end]
  67.         while start < end and arr[start] <= pivot:
  68.             start += 1
  69.         arr[end] = arr[start]
  70.     # 此时start = end
  71.     arr[start] = pivot
  72.     return start

4. 时间复杂度

  • 最优时间复杂度：O(nlogn)
  • 最坏时间复杂度：O(n2)
  • 稳定性：不稳定

    5. 如果让快排看起来稳定

    合理选择pivot：直接随机选基准元素肯定是不合适的。假如对于已经排好序，或者近似排好序的数组，会进入最差情况，时间复杂度O(n2)。
    如果数组小的话，可以从第一项、最后一项、中间一项中取中位数作为基准元素。或者小数组干脆就别用快排，因为递归型的算法会带来额外的开销，在遇到超过1000项的数组是大数组，每隔200个选出一个元素，然后再这些元素中找出中位数

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。

    2. 动图演示

    image.gif排序算法 - 图14

    3. Python 代码实现

    1. def buildMaxHeap(arr):
    2.  import math
    3.  for i in range(math.floor(len(arr)/2),-1,-1):
    4.      heapify(arr,i)
    5. def heapify(arr, i):
    6.  left = 2*i+1
    7.  right = 2*i+2
    8.  largest = i
    9.  if left < arrLen and arr[left] > arr[largest]:
    10.      largest = left
    11.  if right < arrLen and arr[right] > arr[largest]:
    12.      largest = right
    13.  if largest != i:
    14.      swap(arr, i, largest)
    15.      heapify(arr, largest)
    16. def swap(arr, i, j):
    17.  arr[i], arr[j] = arr[j], arr[i]
    18. def heapSort(arr):
    19.  global arrLen
    20.  arrLen = len(arr)
    21.  buildMaxHeap(arr)
    22.  for i in range(len(arr)-1,0,-1):
    23.      swap(arr,0,i)
    24.      arrLen -=1
    25.      heapify(arr, 0)
    26.  return arr

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 动图演示

排序算法 - 图15

2. Python 代码实现

  1. def countingSort(arr, maxValue):
  2.     bucketLen = maxValue+1
  3.     bucket = [0]*bucketLen
  4.     sortedIndex =0
  5.     arrLen = len(arr)
  6.     for i in range(arrLen):
  7.         if not bucket[arr[i]]:
  8.             bucket[arr[i]]=0
  9.         bucket[arr[i]]+=1
  10.     for j in range(bucketLen):
  11.         while bucket[j]>0:
  12.             arr[sortedIndex] = j
  13.             sortedIndex+=1
  14.             bucket[j]-=1
  15.     return arr

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序


基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；

2. LSD 基数排序动图演示


排序算法 - 图16