排序算法 | 排序

直接移动 ( 交换数据位置 )
逻辑移动( 移动指针，更快 )

冒泡排序法 - 交换排序法
从第一个元素开始，比较两个相邻元素的大小，若大小顺序有误，则对调后再进行下一次元素比较，确定最后一个元素位于正确的顺序。接着再进行第二次扫描，直到完成所有元素的排序。
```
  for i in range(len(data)-1, 0, -1):
      for j in range(i):
          if data[j] > data[j+1]:
              data[j], data[j+1] = data[j+1], data[j]
```

选择排序法( Selection Sort )
算是枚举法的应用
反复从未排序的数列中取出最小的元素，加入到另一个数列中。

  for i in range(len(data)-1):
      for j in range(i+1, len(data):
          if data[i] > data[j]:
              data[i], data[j] = data[j], data[i]

插入排序法( Insert Sort )
将数组中的元素逐一与已排好序的数据进行比较，前两个元素先排好，再将第三个元素插入合适的位置，重复直到完成。

  for i in range(1, len(data)):
      tmp = data[i]
      idx = i - 1
      while idx>=0 and tmp < data[idx]:
          data[idx+1] = data[idx] # 把数后置一位，给小数腾地儿
          idx -= 1
      # idx = -1，说明该值是目前最小的，把他放在第一个，即 idx = 0
      data[idx+1] = tmp

希尔排序法( Shell Sort )
可以减少插入排序搬移数据的次数
将数据区分成特定间隔的几个小区快，以插入排序法排完区块内的数据后再渐渐减少隔离的距离。
- 划分数，不一定是 2，质数最好
  8，7，6，5，4，3，2，1
  (8, 4)，(7, 3)，(6, 2)，(5, 1)
  插入排序后
  (4, 8)，(3, 7)，(2, 6)，(1, 5)
  再缩小间隔 (8/2)/2
  (4, 3, 2, 1)，(8, 7, 6, 5)
  插入排序后
  (1, 2, 3, 4)，(5, 6, 7, 8)
```
  jmp = len(data) // 2
  while jmp != 0:
      # 插入排序
      for i in range(jmp, len(data)):
      # for i in range(jmp, len(data), jmp):  # ？？？ 试验的几次都可以成功排序
          tmp = data[i]
          idx = i - jmp
          while idx >= 0 and tmp < data[j]:
              data[j + jmp] = data[j]
              idx -= jmp
          data[idx + jmp] = tmp
      jmp = jmp // 2
```
合并排序法( Merge Sort )
针对以排好序的两个或两个以上的数列（或数据文件），通过合并的方式，将其组合成一个大的且已排好序的数列（或数据文件）。
2 路( 2-way )合并排序：
① 将 N 个长度为 1 的键值，成对的合并成 N/2 个长度为 2 的有序键值组
② 将 N/2 个长度为 2 的键值组，成对的合并成 N/4 个长度为 4 的有序键值组
③ 不断合并，直到键值组长度为 N，且已排好序
```
  # l1, l2 要等长？？？ IndexError: list index out of range
  l3 = []
  idx1 = idx2 = 0
  for i in range(len(l1)+len(l2)-2):
      if l1[idx1] < l2[idx2]:
          l3.append(l1[idx1])
          idx1 += 1
          if idx1 == len(l1):
              l3.extend(l2[idx2:])
              break
      else:
          l3.append(l2[idx2])
          idx2 += 1
          if idx2 == len(l2):
              l3.extend(l1[idx1:])
              break
```

快速排序法( Quick Sort ) - 分割交换排序法
目前公认最佳。使用了分而治之( Divide and Conquer )。
现在数据中找到一个虚拟的中间值，并按此中间值将所有打算排序的数据分为两部分。小于中间值的再左边，大于的再右边。再以同样的方式分别处理左、右两边数据，直到排完序为止。
假设有 n 项记录 R1，R2，R3，...，Rn，其键值为 k1， k2，k3，...，kn：
① 先假设 K 的值为第一个键值
② 从左向右找出键值 Ki，使得 Ki > K
③ 从右向左找出键值 Kj，是的 Kj < K
④ 如果 i < j，那么 Ki 与 Kj 互换，并回到步骤 ②
⑤ 若 i ≥ j，则将 K 与 Kj 互换，并以 j 为基准点分割成左右两部分。然后针对左右两部分进行步骤 ① 至 ⑤，直到左半边键值等于右半边键值

  def quick(d, size, lf, rg):
      # 第一项键值为 d[lf]
      if lf < rg:  # 左右两边
          # ②
          lf_idx = lf + 1
          while d[lf_idx] < d[lf]:
              if lf_idx + 1 == size:
                  break
              lf_idx += 1
          # ③
          rg_idx = rg
          while d[rg_idx] > d[lf]:
              rg_idx -= 1
          # ④
          while lf_idx < rg_idx:
              d[lf_idx], d[rg_idx] = d[rg_idx], d[lf_idx]
              lf_idx += 1
              while d[lf_idx] < d[lf]:
                  lf_idx += 1
              rg_idx -= 1
              while d[rg_idx] > d[lf]:
                  rg_idx -= 1
          # ⑤
          d[lf], d[rg_idx] = d[rg_idx], d[lf]
          quick(d, size, lf, rg_idx-1)
          quick(d, size, rg_idx+1, rg)

基数排序法
并不需要元素间进行比较，属于一种分配模式排序方式。
按比较的方向可分为最高位优先 ( Most Significant Digit First , MSD ) 和最低位优先 ( Least Significant Digit First , LSD ) 两种。
MSD 是从最左边的位数开始比较
LSD 是从最右边的位数开始比较

  def radix(data):
      """三位非负整数比较"""
      n = 1  # n 为基数，从各位开始排序
      while n <= 100:
          tmp = [[None] * 100 for row in range(10)]  # 设置暂存数组 [[n位为0的所有元素], [?1], [?2], ... , [?9]]。[] * 100 规模与元素数目有关
          for i in range(len(data)):
              m = (data[i] // n) % 10  # n 位的数值，n=1为个位，n=10为10位
              tmp[m][i] = data[i]  # 放入棋盘对应位置
          k = 0
          for i in range(10):
              for j in range(len(data)):
                  if tmp[i][j] != None:
                      data[k] = tmp[i][j]  # 读出棋盘里的值，重构数组
                      k += 1
          n *= 10

冒泡、选择、插入排序三种数据搬移量最大的是插入排序。
合并排序法是稳定的。不会改变两个相同数字的原有顺序。