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.
56
｜
第
4
章
图 4-2：使用基于值的存储方式排序
4.1.3 可比较的元素
在待排序的数据集合中，元素必须是全序的。也就是说，对于数据集合里的任意两个元
素
p
和
q
，它们之间的关系只会是以下三种谓词中的一种：
p
=
q
、
p
<
q
或者
p
>
q
。通常，
排序的原生类型包括整数、浮点数和字符。当排序复合元素（如由字符组成的字符串）
时，字典序会应用在它的每一个单个元素上，从而将复杂的排序降为原生类型的排序。
例如，认为单词“
alphabet
”比“
alternate
”小，但是比“
alligator
”大。这是通过从左
到右地比较每一个单个字母，直到其中一个单词没有字母可比较或者两个字母不同为止
（
ant
比
anthem
小就是这个道理）。
排序在碰到如下问题时就会变得十分复杂，例如大小写（“
A
”大于“
a
”吗？）、变音
符（“
è
”小于“
ê
”吗？）和双元音（“
æ
”小于“
a
”吗？）。
Unicode
标准采用了如
UTF-16
的编码来表示单个字符，这样的字符最多占用
4
个字节的存储空间。
Unicode
协
会已经开发了一个叫作“校对算法（
collation algorithm
）”的排序标准，用于处理不同
语言和文化中各种各样的排序规则（
Davis
和
Whistler, 2008
）。
对于本章中讨论的算法，我们假设读者能够提供一个比较函数
cmp
——
用来比较
p
和
q
两个元素：如果
p
=
q
，返回
0
；如果
p
<
q
，返回负数；如果
p
>
q
，
返回正数。如果元
素是复杂结构的数据，
cmp
函数也许只会比较这些元素的“关键值”。例如，机场航站 ...
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.