August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
尾声
：
算法原理
｜
323
尾声：算法
原理
的各种排序算法的性能。这里不仅要关注每种算法在最坏情况下的性能，也要注意在实
现和使用这些算法时所涉及的概念。
表
12
-
1
：排序算法
算法 最好 平均 最差 涉及概念
桶排序
n n n
散列
堆排序
n
log
n n
log
n n
log
n
递归和二叉堆
插入排序
n n
2
n
2
贪心
归并排序
n
log
n n
log
n n
log
n
递归
、
稳定和分治
快速排序
n
log
n n
log
n
n
2
递归和分治
选择排序
n
2
n
2
n
2
贪心
12.2 将问题分解成更小的问题
在进行算法设计时，能够将问题分解成两个（甚至更多）更小的子问题是非常有帮助的。
快速排序
毫无疑问是最流行的排序算法之一。虽然一些精心构造的特例数据会引发其性
能问题，但它还是做到了在大数据集上的平均性能最高。事实上，
O
(
n
log
n
)
的算法都
包含分解问题的思想：先将一个大小为
n
的问题分解为两个
n/
2
的子问题，然后再将两
个子问题的结果汇总作为原问题的结果。要达到
O
(
n
log
n
)
的复杂度，这两个步骤都需
要达到
O
(
n
)
的复杂度才行。
快速排序
是第一个能够达到
O
(
n
log
n
)
性能的原地置换排序算法。它的成功之处就在于
将问题分成两个部分，并递归地通过
快速排序
来解决更小的子问题（听起来似乎有些有
悖常理）。
这种新方法通过简单地将问题一分为二，来获得令人惊异的性能提升。回忆一下
二分查
找
是如何将一个大小为
n
的问题转换为两个大小为
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.