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.
74
｜
第
4
章
3. 处理子数组
快速排序
在切分出来的两个子数组上递归调用
快速排序
。当处理一个子数组时，另一个
的活动记录将会被压入执行栈中。如果较大的子数组首先被处理，那么此时栈中可能存
储了线性数目的活动记录（虽然现代编译器也许会观察到并且消除这个费用）。为了最
小化栈的可能深度，可以先处理较小的子数组。
如果能够预见递归调用的深度会成为问题的话，这说明
快速排序
也许并不适用于你的应
用程序。
4. 为小数组使用简单的插入排序
对于小数组，
插入排序
要比
快速排序
来得快。而对于大数组，
快速排序
最终还是将其切
分成无数的待排序的小数组。为了改善快速排序的递归性能，一个广泛使用的技术是在
排序大子数组时调用快速排序，而在排序小子数组时使用
插入排序
，如例
4-6
所示。
Sedgewick
（
1978
）建议，在快速排序中结合使用三中值和在排序小数组时使用
插入排序
，
可以比纯粹的
快速排序
要快上
20%~25%
。
5. 内观排序
是否切换到对小数组的
插入排序
取决于子数组的大小。
Musser
（
1997
）介绍了一种
快速
排序
的衍生算法——
内观排序
（
IntroSort
），这个算法监视
快速排序
的递归深度，以确
保高效地处理。如果
快速排序
的递归深度超过
log(
n
)
级，那么
内观排序
会切换到
堆排序
。
C++STL
的
SGI
实现就用
内观排序
作为其默认的排序算法。
4.6 不基于比较的排序算法
在本章的结尾，我们将介绍不基于比较的排序算法。这类算法可以在优于
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.