算法 && 排序 入门二

1. 计数排序

计数排序(记一下每个数字出现多少次) 复杂度O（n+max）
优点： 比快排还快
缺点： 需要hash，且只能正整数
例子：

a <- {
  '0': 0,
  '1': 2,
  '2': 1,
  '3': 56,
  '4': 3,
  '5': 67,
  '6': 3,
  'length': 7
}

hash <- {}

index <- 0
while (index < a['length']) 
  number = a[index]    // 0,2,1,56,3...
  if hash[number] === undefined     // hash[number] 不存在
    hash[number] = 1
  else     //  hash[number] 存在
    hash[number] += 1
  end
    index += 1
end

index2 <- 0
max <- findMax(hash)
newArr <- {}

while (index2 < max+1)   // index2 == max(67) 是可以出现的，index2 < 68
  count = hash[index2]
  if count != undefined
    countIndex = 0
    while(countIndex < count)
      newArr.push(index2)
      countIndex += 1
    end
  end
  index2 += 1
end
print newArr

---

2. 桶排序，在计数排序基础上升级，节约空间

hash: {
  1: [0,2,1,3,3],
  2: [],
  3: [],
  4: [],
  5: [],
  6: [56],
  7: [67]
}

3. 基数排序，看个位，再看十位数，再看百位数，入桶出桶，桶的个数是定死的10

4. 堆排序 复杂度O（n*logn）

1. 将每个底部的节点进行比大小，然后再和父节点比大小，把大的放到头部。依次向上对比，形成一个完整的最大堆。
2. 然后把头部最大的拿走，将最右下角的节点，放到头部，然后再从头往下对比大小，直到形成最大堆。
3. 然后再重复2