排序

什么是算法

• 输入： 一个算法必须有0个或以上的输入量
• 输出： 。。。有1个或。。。输出量，是算法计算的结果
• 明确性： 算法的描述是无歧义的，来保证结果匹配要求。
• 有限性： 在有限个步骤内完成
• 有效性： 能够实现

什么是数据结构

数据的结构

1. 有一个要解决的问题
2. 分析这个问题，想出对应的数据结构
3. 分析数据结构，想出算法

大分类

• 分治法： 把一个问题区分成多个部分求解
• 动态规划法： 问题的整体最优解就是由局部最优解组成
• 贪婪算法： 近似求解（可能不是最优解，看起来最容易取得的）
• 线性规划法
• 简并法

排序算法

1. 体育委员两两对比法（冒泡排序）
   • 每次摸两人头，高的往右，低的往前，n*（n-1）*（n-2）...

a = {
  '0': 4,
  '1': 6,
  '2': 3,
  '3': 2,
  '4': 1,
  'length': 5
}
轮数 = 1
index


while (轮数 < a['length']) {
  index = 0 
  while (index <= a['length'] - 1 - 轮数) {
    if (a[index] < a[index+1]) {
      // 什么也不做
    }else{
      // 交换左右的位置
      t = a[index]
      a[index] = a[index+1]
      a[index+1] = t
    }
    index += 1
  }
}

//////
轮数  index的下标最大值（从0开始）
1       3
2       2
3       1
4       0

2. 体育老师一指禅（选择排序）
   • 每次选出队伍里面最矮的人和第一个换位置n*（n-1）*（n-2）...
3. 起扑克牌法（插入排序）（先在里面开一个空数组）
   • 1+2+...+n的排序方法，第一次和一张做对比，第二次和两张牌做对比
4. 强迫症收扑克牌法（计数排序）
   • 最快，放到相应的位置，缺点需要相应的空间，若有13个种类则要13个空间
5. 快排
   • 随便找一个人，比他高的排后面，比他低的排前面。
   • 再以基准的左边或者右边又选一个基准在来排序，分到每堆只剩一个人就完成了
6. 归并排序
7. 堆排序