排序算法

作者: 廖少少 | 来源:发表于2017-06-08 12:28 被阅读1569次

排序算法

冒泡排序
选择排序
插入排序
快速排序（最常见）
希尔排序
归并排序

源码：Sorting

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的思路如下（升序）：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的分析
bubblesort
演示
bubble
时间复杂度
- 最优时间复杂度：O(n) ——表示遍历一次发现没有任何可以交换的元素，排序结束
- 最坏时间复杂度：O(n2)
- 稳定性：稳定

Python 代码

  def bubble_sort(L):
      N = len(L)
      if N <= 0 :
          print("Please input correct list.")
          return
      for i in range(N):
          for j in range(0,N-1-i):
              if L[j] > L[j+1] :
                  L[j],L[j+1] = L[j+1],L[j]
                  print(L)
      return L

  if __name__ == '__main__':
      L = [9,8,7,6,5,4,3,2,1]
      print(bubble_sort(L))

输出

  >>>
  RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\bubble_sort.py
  [8, 9, 7, 6, 5, 4, 3, 2, 1]
  [8, 7, 9, 6, 5, 4, 3, 2, 1]
  [8, 7, 6, 9, 5, 4, 3, 2, 1]
  [8, 7, 6, 5, 9, 4, 3, 2, 1]
  [8, 7, 6, 5, 4, 9, 3, 2, 1]
  [8, 7, 6, 5, 4, 3, 9, 2, 1]
  [8, 7, 6, 5, 4, 3, 2, 9, 1]
  [8, 7, 6, 5, 4, 3, 2, 1, 9]
  [7, 8, 6, 5, 4, 3, 2, 1, 9]
  [7, 6, 8, 5, 4, 3, 2, 1, 9]
  [7, 6, 5, 8, 4, 3, 2, 1, 9]
  [7, 6, 5, 4, 8, 3, 2, 1, 9]
  [7, 6, 5, 4, 3, 8, 2, 1, 9]
  [7, 6, 5, 4, 3, 2, 8, 1, 9]
  [7, 6, 5, 4, 3, 2, 1, 8, 9]
  [6, 7, 5, 4, 3, 2, 1, 8, 9]
  [6, 5, 7, 4, 3, 2, 1, 8, 9]
  [6, 5, 4, 7, 3, 2, 1, 8, 9]
  [6, 5, 4, 3, 7, 2, 1, 8, 9]
  [6, 5, 4, 3, 2, 7, 1, 8, 9]
  [6, 5, 4, 3, 2, 1, 7, 8, 9]
  [5, 6, 4, 3, 2, 1, 7, 8, 9]
  [5, 4, 6, 3, 2, 1, 7, 8, 9]
  [5, 4, 3, 6, 2, 1, 7, 8, 9]
  [5, 4, 3, 2, 6, 1, 7, 8, 9]
  [5, 4, 3, 2, 1, 6, 7, 8, 9]
  [4, 5, 3, 2, 1, 6, 7, 8, 9]
  [4, 3, 5, 2, 1, 6, 7, 8, 9]
  [4, 3, 2, 5, 1, 6, 7, 8, 9]
  [4, 3, 2, 1, 5, 6, 7, 8, 9]
  [3, 4, 2, 1, 5, 6, 7, 8, 9]
  [3, 2, 4, 1, 5, 6, 7, 8, 9]
  [3, 2, 1, 4, 5, 6, 7, 8, 9]
  [2, 3, 1, 4, 5, 6, 7, 8, 9]
  [2, 1, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>>

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
选择排序分析
selectionsort
演示
selection
时间复杂度
- 最优时间复杂度：O(n2)
- 最坏时间复杂度：O(n2)
- 稳定性：不稳定（考虑升序每次选择最大的情况）

Python 代码

  def select_sort(L):
      N = len(L)
      if N <= 0 :
          print("Please input correct list.")
          return
      for i in range(N-1):
          indexOfMax = 0
          for j in range(1,N-i):
              if L[j] > L[indexOfMax] :
                  indexOfMax = j
          L[N-1-i], L[indexOfMax] = L[indexOfMax], L[N-1-i]
          print(L)
      return L

  if __name__ == '__main__':
      L = [9,8,7,6,5,4,3,2,1]
      select_sort(L)

输出

  >>>
  RESTART: F:/杂/markdown/Python/DataStructure&Algorithm/Sorting/selection_sort.py
  [1, 8, 7, 6, 5, 4, 3, 2, 9]
  [1, 2, 7, 6, 5, 4, 3, 8, 9]
  [1, 2, 3, 6, 5, 4, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>>

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，对于少量元素，它是一种有效的算法。
想像一下，我们在打扑克牌，首先我们手上没有牌，然后一张一张从桌上摸牌，每次摸牌都会按照从小到大的顺序排好，所以手上的牌总是有序的。
它的工作原理：
- 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
演示
Insertion-sort-example

伪代码

  INSERTION-SORT(A)
      for j = 2 to A.length
          key = A[j]
          //Insert A[j] into the sorted sequence A[1..j-1].
          i = j - 1
          while i > 0 and A[i] > key
              A[i+1] = A[i]
              i = i - 1
          A[i+1] = key

时间复杂度
- 最优时间复杂度：O(n) ——升序排列，序列已经处于升序状态
- 最坏时间复杂度：O(n2) ——序列处于降序状态，要转变为升序
- 稳定性：稳定

Python 代码

  def insertion_sort(L):
      N = len(L)
      if N <= 0:
          print("Please input correct list.")
          return
      for i in range(N): # i指示当前待排元素
          if L[i - 1] < L[i]: # 如果待排元素比已排序列的最后一个元素（最大的元素）还大，则直接加入已排序列
              continue
          temp = L[i]
          for j in range(i - 1, -1, -1): # i-1指示已排序列的最后一项，然后以此与当前待排元素比较，往前移动
              L[j + 1] = L[j]
              if L[j - 1] <= temp:
                  L[j] = temp
                  print(L)
                  break
      return L

  if __name__ == '__main__':
      L = [1, 8, 7, 6, 5, 4, 3, 2, 1]
      print("ordered sequence =",insertion_sort(L))

输出

  >>>
  RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\insertion_sort.py
  [8, 9, 7, 6, 5, 4, 3, 2, 1]
  [7, 8, 9, 6, 5, 4, 3, 2, 1]
  [6, 7, 8, 9, 5, 4, 3, 2, 1]
  [5, 6, 7, 8, 9, 4, 3, 2, 1]
  [4, 5, 6, 7, 8, 9, 3, 2, 1]
  [3, 4, 5, 6, 7, 8, 9, 2, 1]
  [2, 3, 4, 5, 6, 7, 8, 9, 1]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>>

快速排序（最常见）

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），或称枢纽
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
时间复杂度
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n2) ——每次分区时，某个分区为空
- 稳定性：不稳定
从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中走访过一次，使用O(n)的时间。在使用结合（concatenation）的版本中，这项运算也是O(n)。
在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中，不会处理到原来数列的相同部分；因此，程序调用的每一层次结构总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一层次结构仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。

Python 代码

  def quick_sort(L):
      return qsort(L,0,len(L)-1)

  def qsort(L,low,high):
      if(low < high):
          pivotloc = partition(L,low,high)
          qsort(L,low,pivotloc-1)
          qsort(L,pivotloc+1,high)
      return L

  def partition(L,low,high):
      if(low >= high):
          return
      pivotkey = L[low]
      while(low < high):
          while(low < high and L[high] >= pivotkey):
              high = high - 1
          L[low],L[high] = L[high],L[low]
          while(low < high and L[low] <= pivotkey):
              low = low + 1
          L[high],L[low] = L[low],L[high]
          print("pivotkey =",pivotkey)
          print(L,"\n")
      return low

  if __name__ == '__main__':
      L = [9,8,7,6,5,4,3,2,1]
      print(quick_sort(L))

输出

  >>>
  RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\quick_sort.py
  pivotkey = 9
  [1, 8, 7, 6, 5, 4, 3, 2, 9]

  pivotkey = 1
  [1, 8, 7, 6, 5, 4, 3, 2, 9]

  pivotkey = 8
  [1, 2, 7, 6, 5, 4, 3, 8, 9]

  pivotkey = 2
  [1, 2, 7, 6, 5, 4, 3, 8, 9]

  pivotkey = 7
  [1, 2, 3, 6, 5, 4, 7, 8, 9]

  pivotkey = 3
  [1, 2, 3, 6, 5, 4, 7, 8, 9]

  pivotkey = 6
  [1, 2, 3, 4, 5, 6, 7, 8, 9]

  pivotkey = 4
  [1, 2, 3, 4, 5, 6, 7, 8, 9]

  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>>

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
基本思想：先将整个待排序列分割称为若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序
希尔排序过程
- 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
- 例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：
```
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
```
  然后我们对每列进行排序：
```
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
```
  将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
```
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
```
  排序之后变为：
```
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
```
  最后以1步长进行排序（此时就是简单的插入排序了）
时间复杂度
- 最优时间复杂度：根据步长序列的不同而不同
- 最坏时间复杂度：O(n2)
- 稳定性：不稳定

Python 代码

  def shell_sort(L,delta):
      N = len(L)
      for inc in delta:
          L = shell_insert(L,inc)
          print(L,"\n")
      return L

  def shell_insert(L,inc):
      N = len(L)
      for index in range(inc):               # 整个序列分为若干子序列，index是每个子序列的头元素
          for i in range(index+inc,N,inc):   # 默认每个子序列的头元素为“已排序列”，除了头元素的子序列为“待排序列”
              temp = L[i]                    # 每个子序列的排序方式为直接插入排序，所以当前待排元素的值给temp
              for j in range(i-inc,-1,-inc): # 在子序列的“已排序列”中找到合适的插入地点，所以是倒序
                  if temp < L[j]:
                      L[j+inc] = L[j]
                  else :
                      break                  # 当前待排元素比“已排序列”中的末尾元素还要大，所以直接放入末尾
                  if j == index or L[j-inc] < temp :
                      L[j] = temp
                      print(L)
      return L

  if __name__ == '__main__':
      L = [9,8,7,6,5,4,3,2,1]
      delta = [5,3,1] #构造增量序列
      print(shell_sort(L,delta))

输出

  >>>
  RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\shell_sort.py
  [4, 8, 7, 6, 5, 9, 3, 2, 1]
  [4, 3, 7, 6, 5, 9, 8, 2, 1]
  [4, 3, 2, 6, 5, 9, 8, 7, 1]
  [4, 3, 2, 1, 5, 9, 8, 7, 6]
  [4, 3, 2, 1, 5, 9, 8, 7, 6]

  [1, 3, 2, 4, 5, 9, 8, 7, 6]
  [1, 3, 2, 4, 5, 6, 8, 7, 9]
  [1, 3, 2, 4, 5, 6, 8, 7, 9]

  [1, 2, 3, 4, 5, 6, 8, 7, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  [1, 2, 3, 4, 5, 6, 7, 8, 9]

  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  >>>

归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
归并排序的分析
Merge-sort-example
时间复杂度
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 稳定性：稳定
- 缺点:占用了一定的空间，所以归并算法是用空间换取时间的典型应用

Python 代码

  def merge(left, right):
      lp, rp = 0, 0
      result = []
      while lp < len(left) and rp < len(right):
          if left[lp] <= right[rp]:
              result.append(left[lp])
              lp += 1
          else:
              result.append(right[rp])
              rp += 1
      result += left[lp:]
      result += right[rp:]
      return result

  def merge_sort(alist):
      length = len(alist)
      if length == 1:
          return alist
      mid = length // 2
      left = merge_sort(alist[:mid])
      right = merge_sort(alist[mid:])
      print("left = %s, right = %s"%(left,right))
      result = merge(left, right)
      print("merge:",result)
      return result

  if __name__ == '__main__':
      alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
      print("ordered sequence =",merge_sort(alist))

输出

  left = [9], right = [8]
  merge: [8, 9]
  left = [7], right = [6]
  merge: [6, 7]
  left = [8, 9], right = [6, 7]
  merge: [6, 7, 8, 9]
  left = [5], right = [4]
  merge: [4, 5]
  left = [2], right = [1]
  merge: [1, 2]
  left = [3], right = [1, 2]
  merge: [1, 2, 3]
  left = [4, 5], right = [1, 2, 3]
  merge: [1, 2, 3, 4, 5]
  left = [6, 7, 8, 9], right = [1, 2, 3, 4, 5]
  merge: [1, 2, 3, 4, 5, 6, 7, 8, 9]
  ordered sequence = [1, 2, 3, 4, 5, 6, 7, 8, 9]

各种排序算法效率比较

2017911-排序比较

算法是否稳定：待排序列中同样元素的先后顺序是否改变

比如待排序列是：2，3，1，8，9，1'

排列后的序列是：1'，1，2，3，8，9
快速排序应用广泛的原因：
- 性能接近 O(nlogn)
- 辅助空间较归并排序小
- 一般不太关注稳定与否

网友评论

84bfd4c7883a:真的能懂，目前长沙学java3个月
zhangsan5421:你用简短的python语言就把基础的算法实现了。非常使用。你在长沙？
廖少少: @zhangsan5421 哈哈，谢谢夸奖，之前学Java，最近开始接触Python，感觉挺好的
zhangsan5421:@廖少少你是一个很棒的小伙子。同时，Python 值得好好学习。
廖少少: @zhangsan5421 Python的特点就是简短嘛，我还在广州读书
提莫酱T:动画真的比代码好理解，哈哈
提莫酱T:@廖少少谢谢
廖少少: @一路坦途 😄是的，有个网站你可以去看看visualgo.net
大桥酱:挺好的
大桥酱:@廖少少搞个堆排
廖少少: @大桥酱谢谢支持
logname:动画很生动
廖少少: @logname 可以去visualgo.net看看动画，那个很强大
lerko_:这个是我见过描述最为清晰的排序算法总结了，赞一个
廖少少: 学习过程中做的笔记而已，所以没有用严谨的定义式，能让人看懂是我的目标
14bf7199f818:好文！已收入《iOS - 大杂烩》专题，感谢作者的分享！
———————————————————————————————
不定期更新高质量文章，欢迎投稿关注，更多iOS专项专题：
http://www.jianshu.com/c/563ba4d42d38[iOS - 大杂烩]
http://www.jianshu.com/c/1fee819318a7[iOS - 内存/数据/存储]
http://www.jianshu.com/c/6a28d1d173b5[iOS - 线程/底层]
http://www.jianshu.com/c/4dd5a67bbe1d[iOS - 音视频/图文/动画]
http://www.jianshu.com/c/2de7446d0de9[iOS - 网络处理]
http://www.jianshu.com/c/5458bca566a9[iOS - 安全/逆向]
http://www.jianshu.com/c/ca237eb95714[iOS - 优化/质量]
14bf7199f818:@阿群1986 后面再加
阿群1986: @youngliuxx iOS似乎缺少Python工具