search

lewenweijia / notes

🏊 dive dive diving
1 stars 0 forks source link

重新认识排序 #34

Open lewenweijia opened 5 years ago

lewenweijia commented 5 years ago

内排序: 冒泡/插入/选择/快排/归并/堆/希尔 -> 考量因素: 比较次数 外排序: 桶排序/基数排序/计数排序 -> 考量因素: 比较次数 + IO次数(硬盘读写速度)

外排优化点: 减少外存的写入次数(多路归并, 内存可以容纳四个元素, 那么思路归并)

lewenweijia commented 5 years ago

趣谈外部排序

lewenweijia commented 5 years ago

外部排序案例

  1. 百万订单数据(订单金额分布不一致)
  2. 百万考生分数
lewenweijia commented 5 years ago 
快排? -> partition
归并? -> merge
KMP? -> next 数组 (最长公共前后缀数组/longest prefix suffix array)