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.
排序算法
｜
61
排序算法
由于现实世界中的许多数据都已经是部分有序了，因此乐观主义和现实主义让我们觉得
插入排序
可以作为一种高效的算法去使用。
插入排序
的性能会随着重复元素的增加而提
升，因为重复元素的增加意味着所需要执行的交换操作更少。
但是，当所有
n
个元素互不相同或者数组被随机组织（即数据的所有排列等概率出现）时，
插入排序
会显得有些过于保守，因为这种情况下每个元素距离其最终位置的平均距离是
n
/3
。代码库中的
numTranspositions.c
程序对于较小的
n
（
n
≤
12
）实证验证了这种说
法（同样可以参考
Trivedi
，
2001
）。在平均情况和最坏情况下，
n
个元素都需要移动线
性数量的位置，因此
插入排序
需要
O
(
n
2
)
平方级的时间。
插入排序
对于基于值的数据处理效率很低，因为它需要移动大量的内存来给新值腾出空
间。表
4-3
给出了基于值方式的插入排序实现与例
4-2
中的指针实现的对比结果。我们
执行了
10
次随机实验，每次实验对
n
个元素进行排序，并除去最好结果和最坏结果。
表中数据为剩余
8
次结果的平均值。注意观察该实现是如何通过内存块移动而非单独的
内存交换来改善性能的。随着数组的大小增加一倍，执行时间大约变为原来的
4
倍，这
正好验证了
插入排序
算法的
O
(
n
2
)
性能。要注意的是，即使使用内存块移动来改善性能，
插入排序
依旧是平方级性能。
表
4
-
3
：块移动的插入排序和原生插入排序的性能对比
n
/ 个 块移动的插入排序（
B
n
）/s 原生插入排序（
S
n
）/s
1,024 0.0039 0.0130
2,048 0.0153 ...
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.