Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

重新认识排序 #34

Open
lewenweijia opened this issue Oct 19, 2019 · 3 comments
Open

重新认识排序 #34

lewenweijia opened this issue Oct 19, 2019 · 3 comments

Comments

@lewenweijia
Copy link
Owner

lewenweijia commented Oct 19, 2019 •
edited
Loading

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

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

趣谈外部排序

@lewenweijia
Copy link
Owner Author

外部排序案例

  1. 百万订单数据(订单金额分布不一致)
  2. 百万考生分数

@lewenweijia
Copy link
Owner Author

lewenweijia commented Oct 21, 2019 •
edited
Loading 

快排? -> partition
归并? -> merge
KMP? -> next 数组 (最长公共前后缀数组/longest prefix suffix array)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@lewenweijia