添加排序一章

2 files changed, 585 insertions, 62 deletions

diff --git a/LectureNotesOnPython.html b/LectureNotesOnPython.html
index be18d22..f56596b 100644
--- a/LectureNotesOnPython.html
+++ b/LectureNotesOnPython.html
@@ -370,52 +370,64 @@ ul.auto-toc {
 <tr><th class="docinfo-name">Authors:</th>
 <td>蓝珲 (lanhui AT zjnu.edu.cn)</td></tr>
 <tr><th class="docinfo-name">Version:</th>
-<td>0.1.1 of 2019-04-14</td></tr>
+<td>0.1.2 of 2019-04-14</td></tr>
 </tbody>
 </table>
 <div class="contents topic" id="id1">
 <p class="topic-title first">内容目录</p>
 <ul class="simple">
-<li><a class="reference internal" href="#id2" id="id18">前言</a></li>
-<li><a class="reference internal" href="#python" id="id19">Python的发音纠正</a></li>
-<li><a class="reference internal" href="#id3" id="id20">Python源流</a></li>
-<li><a class="reference internal" href="#id4" id="id21">Python的关键词</a></li>
-<li><a class="reference internal" href="#id5" id="id22">值的类型</a></li>
-<li><a class="reference internal" href="#variable" id="id23">变量（Variable）</a></li>
-<li><a class="reference internal" href="#mutable" id="id24">可变（mutable）类型与不可变类型</a></li>
-<li><a class="reference internal" href="#id6" id="id25">数与格式化显示</a></li>
-<li><a class="reference internal" href="#strings" id="id26">字符串（Strings）</a></li>
-<li><a class="reference internal" href="#concatenation" id="id27">字符串相加（concatenation）</a></li>
-<li><a class="reference internal" href="#slice" id="id28">子串（slice）</a></li>
-<li><a class="reference internal" href="#id7" id="id29">搜索字符串</a></li>
-<li><a class="reference internal" href="#string" id="id30">String类（对象）方法</a></li>
-<li><a class="reference internal" href="#in" id="id31">in操作符</a></li>
-<li><a class="reference internal" href="#id8" id="id32">字符串比较</a></li>
-<li><a class="reference internal" href="#id9" id="id33">列表</a></li>
-<li><a class="reference internal" href="#id10" id="id34">列表作为参数</a></li>
-<li><a class="reference internal" href="#append" id="id35">注意区别 <tt class="docutils literal">append</tt> 与 <tt class="docutils literal">+</tt> 操作符</a><ul>
-<li><a class="reference internal" href="#tdd-test-driven-development" id="id36">TDD - Test-driven Development</a></li>
-<li><a class="reference internal" href="#id11" id="id37">计算复杂度</a></li>
+<li><a class="reference internal" href="#id2" id="id24">前言</a></li>
+<li><a class="reference internal" href="#python" id="id25">Python的发音纠正</a></li>
+<li><a class="reference internal" href="#id3" id="id26">Python源流</a></li>
+<li><a class="reference internal" href="#id4" id="id27">Python的关键词</a></li>
+<li><a class="reference internal" href="#id5" id="id28">值的类型</a></li>
+<li><a class="reference internal" href="#variable" id="id29">变量（Variable）</a></li>
+<li><a class="reference internal" href="#mutable" id="id30">可变（mutable）类型与不可变类型</a></li>
+<li><a class="reference internal" href="#id6" id="id31">数与格式化显示</a></li>
+<li><a class="reference internal" href="#strings" id="id32">字符串（Strings）</a></li>
+<li><a class="reference internal" href="#concatenation" id="id33">字符串相加（concatenation）</a></li>
+<li><a class="reference internal" href="#slice" id="id34">子串（slice）</a></li>
+<li><a class="reference internal" href="#id7" id="id35">搜索字符串</a></li>
+<li><a class="reference internal" href="#string" id="id36">String类（对象）方法</a></li>
+<li><a class="reference internal" href="#in" id="id37">in操作符</a></li>
+<li><a class="reference internal" href="#id8" id="id38">字符串比较</a></li>
+<li><a class="reference internal" href="#id9" id="id39">列表</a></li>
+<li><a class="reference internal" href="#id10" id="id40">列表作为参数</a></li>
+<li><a class="reference internal" href="#append" id="id41">注意区别 <tt class="docutils literal">append</tt> 与 <tt class="docutils literal">+</tt> 操作符</a><ul>
+<li><a class="reference internal" href="#tdd-test-driven-development" id="id42">TDD - Test-driven Development</a></li>
+<li><a class="reference internal" href="#id11" id="id43">计算复杂度</a></li>
 </ul>
 </li>
-<li><a class="reference internal" href="#dictionary" id="id38">字典（Dictionary）</a><ul>
-<li><a class="reference internal" href="#incremental-development" id="id39">递增开发（Incremental Development）</a></li>
-<li><a class="reference internal" href="#keyvalue" id="id40">key与value互换</a></li>
-<li><a class="reference internal" href="#id12" id="id41">字典里面可以有字典</a></li>
+<li><a class="reference internal" href="#dictionary" id="id44">字典（Dictionary）</a><ul>
+<li><a class="reference internal" href="#incremental-development" id="id45">递增开发（Incremental Development）</a></li>
+<li><a class="reference internal" href="#keyvalue" id="id46">key与value互换</a></li>
+<li><a class="reference internal" href="#id12" id="id47">字典里面可以有字典</a></li>
 </ul>
 </li>
-<li><a class="reference internal" href="#id13" id="id42">函数</a><ul>
-<li><a class="reference internal" href="#id14" id="id43">局部变量</a></li>
-<li><a class="reference internal" href="#id15" id="id44">全局变量</a></li>
-<li><a class="reference internal" href="#id16" id="id45">调用函数与传递参数</a></li>
-<li><a class="reference internal" href="#flow-of-execution" id="id46">函数执行顺序 （flow of execution）</a></li>
+<li><a class="reference internal" href="#id13" id="id48">函数</a><ul>
+<li><a class="reference internal" href="#id14" id="id49">局部变量</a></li>
+<li><a class="reference internal" href="#id15" id="id50">全局变量</a></li>
+<li><a class="reference internal" href="#id16" id="id51">调用函数与传递参数</a></li>
+<li><a class="reference internal" href="#flow-of-execution" id="id52">函数执行顺序 （flow of execution）</a></li>
 </ul>
 </li>
-<li><a class="reference internal" href="#id17" id="id47">参考</a></li>
+<li><a class="reference internal" href="#id17" id="id53">排序</a><ul>
+<li><a class="reference internal" href="#id18" id="id54">排序一组数或一组字符串</a></li>
+<li><a class="reference internal" href="#id19" id="id55">自定义排序算法</a><ul>
+<li><a class="reference internal" href="#id20" id="id56">选择排序</a></li>
+<li><a class="reference internal" href="#merge-sort" id="id57">合并排序 （Merge sort）</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#id21" id="id58">比较排序速度</a></li>
+<li><a class="reference internal" href="#id22" id="id59">排序元组列表</a></li>
+<li><a class="reference internal" href="#lambda" id="id60">巧用 lambda 函数进行灵活排序</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#id23" id="id61">参考</a></li>
 </ul>
 </div>
 <div class="section" id="id2">
-<h1><a class="toc-backref" href="#id18">前言</a></h1>
+<h1><a class="toc-backref" href="#id24">前言</a></h1>
 <p>非学究写书，无空洞行文。</p>
 <p>Python语法简洁，库函数全面强大，编程速度快，运行速度也不慢。</p>
 <p>大学里， 往往是专家教初学者。 专家也是从初学者过来的，只不过专家经常忘
@@ -437,12 +449,12 @@ ul.auto-toc {
 初学者说“我明白了”。</p>
 </div>
 <div class="section" id="python">
-<h1><a class="toc-backref" href="#id19">Python的发音纠正</a></h1>
+<h1><a class="toc-backref" href="#id25">Python的发音纠正</a></h1>
 <p>国人普遍把th发作s。 Not quite correct。</p>
 <p>ˈpī-ˌthän , -thən <a class="reference external" href="https://cn.bing.com/search?q=define%20python&amp;tf=U2VydmljZT1EaWN0aW9uYXJ5QW5zd2VyVjIgU2NlbmFyaW89RGVmaW5pdGlvblNjZW5hcmlvIFBvc2l0aW9uPU5PUCBSYW5raW5nRGF0YT1UcnVlIEZvcmNlUGxhY2U9RmFsc2UgUGFpcnM9RGljdGlvbmFyeVdvcmQ6cHl0aG9uO3NjbjpEZWZpbml0aW9uU2NlbmFyaW87cDpRQVM7IHw%3d&amp;hs=hyRBF0mYq9hrfQUq66DIZnFVta1ZGRfBiBks25oUguk%3d">pronounciation</a></p>
 </div>
 <div class="section" id="id3">
-<h1><a class="toc-backref" href="#id20">Python源流</a></h1>
+<h1><a class="toc-backref" href="#id26">Python源流</a></h1>
 <p>Python之父Guido van Rossum，荷兰人，1956年生，1982年阿姆斯特丹大学获得
 数学与计算机科学硕士学位。有过ABC语言的工作经验。1989年设计了Python语
 言。</p>
@@ -492,7 +504,7 @@ ul.auto-toc {
 </blockquote>
 </div>
 <div class="section" id="id4">
-<h1><a class="toc-backref" href="#id21">Python的关键词</a></h1>
+<h1><a class="toc-backref" href="#id27">Python的关键词</a></h1>
 <div class="line-block">
 <div class="line">def pass</div>
 <div class="line">from import</div>
@@ -514,7 +526,7 @@ ul.auto-toc {
 <p>关键词被语言留用（reserved），无法作变量名。</p>
 </div>
 <div class="section" id="id5">
-<h1><a class="toc-backref" href="#id22">值的类型</a></h1>
+<h1><a class="toc-backref" href="#id28">值的类型</a></h1>
 <p>所有的值都是对象。a = 5, help(a)  a.bit_length()</p>
 <p>数字。1， 1.，1.1， .1, 1e1, 1e-1, 1E1, 1E-1</p>
 <dl class="docutils">
@@ -534,7 +546,7 @@ A list of objects</dd>
 <p>元组（tuple），字典（dict）。</p>
 </div>
 <div class="section" id="variable">
-<h1><a class="toc-backref" href="#id23">变量（Variable）</a></h1>
+<h1><a class="toc-backref" href="#id29">变量（Variable）</a></h1>
 <p>是一个名字（name），是指向一个值（value）的名字。</p>
 <p>值存放在内存（memory）中的某个地址。</p>
 <p>尽量选有意义的简短的名字。比如，代表个数用n，代表索引用i，j，k。</p>
@@ -623,7 +635,7 @@ A list of objects</dd>
 </ul>
 </div>
 <div class="section" id="mutable">
-<h1><a class="toc-backref" href="#id24">可变（mutable）类型与不可变类型</a></h1>
+<h1><a class="toc-backref" href="#id30">可变（mutable）类型与不可变类型</a></h1>
 <p>字符串是不可变的（immutable）类型，不能在原内存地址改变。</p>
 <p>a = 'hello'  不可以原地修改a[0] = 'H'。需要修改a的值时，需要对a进行重新赋值a = 'Hello'。</p>
 <p>列表是可变（mutable）类型，能在原内存地址改变。</p>
@@ -648,7 +660,7 @@ A list of objects</dd>
 </blockquote>
 </div>
 <div class="section" id="id6">
-<h1><a class="toc-backref" href="#id25">数与格式化显示</a></h1>
+<h1><a class="toc-backref" href="#id31">数与格式化显示</a></h1>
 <blockquote>
 <div class="line-block">
 <div class="line">x = 3.1415926</div>
@@ -696,7 +708,7 @@ A list of objects</dd>
 </blockquote>
 </div>
 <div class="section" id="strings">
-<h1><a class="toc-backref" href="#id26">字符串（Strings）</a></h1>
+<h1><a class="toc-backref" href="#id32">字符串（Strings）</a></h1>
 <p>由字符组成。</p>
 <div class="line-block">
 <div class="line">fruit = 'banana!'</div>
@@ -752,7 +764,7 @@ A list of objects</dd>
 <p>以上 <tt class="docutils literal"># [start,stop,step]</tt> 代表注释（comment），注释以 <tt class="docutils literal">#</tt> 号开头。</p>
 </div>
 <div class="section" id="concatenation">
-<h1><a class="toc-backref" href="#id27">字符串相加（concatenation）</a></h1>
+<h1><a class="toc-backref" href="#id33">字符串相加（concatenation）</a></h1>
 <p>输出Jack, Kack, Lack, Mack, Nack, Ouack, Pack, and Quack</p>
 <div class="line-block">
 <div class="line">prefixes = 'JKLMNOPQ'</div>
@@ -771,7 +783,7 @@ A list of objects</dd>
 </div>
 </div>
 <div class="section" id="slice">
-<h1><a class="toc-backref" href="#id28">子串（slice）</a></h1>
+<h1><a class="toc-backref" href="#id34">子串（slice）</a></h1>
 <p>s[n:m]，其中n或m可省略。
 包括第n个字符，不包括第m个字符。（索引自0开始）</p>
 <div class="line-block">
@@ -795,7 +807,7 @@ A list of objects</dd>
 </div>
 </div>
 <div class="section" id="id7">
-<h1><a class="toc-backref" href="#id29">搜索字符串</a></h1>
+<h1><a class="toc-backref" href="#id35">搜索字符串</a></h1>
 <div class="line-block">
 <div class="line">def find(word, c):</div>
 <div class="line-block">
@@ -821,7 +833,7 @@ A list of objects</dd>
 <p>练习：用上面三参数的find来做。</p>
 </div>
 <div class="section" id="string">
-<h1><a class="toc-backref" href="#id30">String类（对象）方法</a></h1>
+<h1><a class="toc-backref" href="#id36">String类（对象）方法</a></h1>
 <div class="line-block">
 <div class="line">upper()</div>
 <div class="line">lower()</div>
@@ -834,14 +846,14 @@ A list of objects</dd>
 </div>
 </div>
 <div class="section" id="in">
-<h1><a class="toc-backref" href="#id31">in操作符</a></h1>
+<h1><a class="toc-backref" href="#id37">in操作符</a></h1>
 <p>'a' in 'banana'
 'seed' in 'banana'</p>
 <p>练习：写出下面的函数，使得
 in_both('apples', 'oranges')返回'aes'。</p>
 </div>
 <div class="section" id="id8">
-<h1><a class="toc-backref" href="#id32">字符串比较</a></h1>
+<h1><a class="toc-backref" href="#id38">字符串比较</a></h1>
 <p>字典序（alphabetical order）。大写字母排在小写字母前。</p>
 <p>字符串之间可以有以下对比操作:</p>
 <div class="line-block">
@@ -857,7 +869,7 @@ in_both('apples', 'oranges')返回'aes'。</p>
 <p>即兴定义函数，制造一个长度不小于4的密码。</p>
 </div>
 <div class="section" id="id9">
-<h1><a class="toc-backref" href="#id33">列表</a></h1>
+<h1><a class="toc-backref" href="#id39">列表</a></h1>
 <p>语言的内置（built-in）类型。注意与String类比，index也是从0开始， in操作符， 求长度，获得字串，遍历操作类似。</p>
 <blockquote>
 <div class="line-block">
@@ -975,7 +987,7 @@ a与b是指向[1,2,3]的两个references。
 error-prone（易错）</p>
 </div>
 <div class="section" id="id10">
-<h1><a class="toc-backref" href="#id34">列表作为参数</a></h1>
+<h1><a class="toc-backref" href="#id40">列表作为参数</a></h1>
 <blockquote>
 <div class="line-block">
 <div class="line">def delete_head(t):</div>
@@ -991,7 +1003,7 @@ error-prone（易错）</p>
 </blockquote>
 </div>
 <div class="section" id="append">
-<h1><a class="toc-backref" href="#id35">注意区别 <tt class="docutils literal">append</tt> 与 <tt class="docutils literal">+</tt> 操作符</a></h1>
+<h1><a class="toc-backref" href="#id41">注意区别 <tt class="docutils literal">append</tt> 与 <tt class="docutils literal">+</tt> 操作符</a></h1>
 <blockquote>
 <div class="line-block">
 <div class="line">t1 = [1, 2]</div>
@@ -1018,7 +1030,7 @@ error-prone（易错）</p>
 </dl>
 </blockquote>
 <div class="section" id="tdd-test-driven-development">
-<h2><a class="toc-backref" href="#id36">TDD - Test-driven Development</a></h2>
+<h2><a class="toc-backref" href="#id42">TDD - Test-driven Development</a></h2>
 <p>测试驱动开发。 My favourite。 刺激有挑战性。 帮助厘清需求。  帮助编写代码。</p>
 <p>推荐使用pytest。如何安装？ 使用命令 <tt class="docutils literal">pip install pytest</tt>。</p>
 <p>在 <tt class="docutils literal">test_cases.py</tt> 写如下测试用例。然后在命令行运行： <tt class="docutils literal">python <span class="pre">-m</span> pytest test_cases.py</tt> 。</p>
@@ -1058,13 +1070,13 @@ error-prone（易错）</p>
 </pre>
 </div>
 <div class="section" id="id11">
-<h2><a class="toc-backref" href="#id37">计算复杂度</a></h2>
+<h2><a class="toc-backref" href="#id43">计算复杂度</a></h2>
 <p>用Big O表述复杂度。O(n)， O(n^2), O(n^3)。</p>
 <p>密码实验回顾。</p>
 </div>
 </div>
 <div class="section" id="dictionary">
-<h1><a class="toc-backref" href="#id38">字典（Dictionary）</a></h1>
+<h1><a class="toc-backref" href="#id44">字典（Dictionary）</a></h1>
 <p>Mutable数据类型。</p>
 <p>实际开发中超级有用。</p>
 <blockquote>
@@ -1088,7 +1100,7 @@ error-prone（易错）</p>
 <p>key-value pair (item)</p>
 <p>item的顺序不可预测，不是按照创建时的顺序。</p>
 <div class="section" id="incremental-development">
-<h2><a class="toc-backref" href="#id39">递增开发（Incremental Development）</a></h2>
+<h2><a class="toc-backref" href="#id45">递增开发（Incremental Development）</a></h2>
 <p>每次完成一小点。从易到难。</p>
 <p>练习：给定一个字符串，数出每个字母出现的频率。</p>
 <pre class="code python literal-block">
@@ -1196,7 +1208,7 @@ error-prone（易错）</p>
 <p>练习： 改写函数 <tt class="docutils literal">word_frequency</tt> ， 使它能接受第三个参数， <tt class="docutils literal">black_lst</tt>。 <tt class="docutils literal">black_lst</tt> 是包含要排除考虑的单词的列表。 例如， <tt class="docutils literal">black_lst</tt> 可以是 <tt class="docutils literal">['the', 'and', 'of', 'to']</tt> 。</p>
 </div>
 <div class="section" id="keyvalue">
-<h2><a class="toc-backref" href="#id40">key与value互换</a></h2>
+<h2><a class="toc-backref" href="#id46">key与value互换</a></h2>
 <p>注意到在原来的字典中一个value可能对应多个key的值。比如 <tt class="docutils literal">d = <span class="pre">{'a':1,</span> <span class="pre">'b':2,</span> <span class="pre">'c':2}</span></tt> 中，2就对应两个key，'b'与'c'。</p>
 <pre class="code python literal-block">
 <span class="keyword">def</span> <span class="name function">inverse_dictionary</span><span class="punctuation">(</span><span class="name">d</span><span class="punctuation">):</span>
@@ -1233,14 +1245,14 @@ error-prone（易错）</p>
 </pre>
 </div>
 <div class="section" id="id12">
-<h2><a class="toc-backref" href="#id41">字典里面可以有字典</a></h2>
+<h2><a class="toc-backref" href="#id47">字典里面可以有字典</a></h2>
 <pre class="code python literal-block">
 <span class="name">d</span> <span class="operator">=</span> <span class="punctuation">{</span> <span class="literal string single">'john'</span><span class="punctuation">:{</span><span class="literal string single">'dob'</span><span class="punctuation">:</span><span class="literal string single">'1990-10-23'</span><span class="punctuation">,</span> <span class="literal string single">'height'</span><span class="punctuation">:</span><span class="literal string single">'6 feet 5 inches'</span><span class="punctuation">}</span> <span class="punctuation">}</span>
 </pre>
 </div>
 </div>
 <div class="section" id="id13">
-<h1><a class="toc-backref" href="#id42">函数</a></h1>
+<h1><a class="toc-backref" href="#id48">函数</a></h1>
 <p>当我们开始不断复制黏贴代码时，就要考虑把这部分代码做成函数了。</p>
 <p>函数 <tt class="docutils literal">unique_words</tt> 与 <tt class="docutils literal">unique_words2</tt> 哪个运行速度快？</p>
 <pre class="code python literal-block">
@@ -1259,11 +1271,11 @@ error-prone（易错）</p>
 <span class="keyword">print</span><span class="punctuation">(</span><span class="name">unique_words2</span><span class="punctuation">([</span><span class="literal string single">'hello'</span><span class="punctuation">,</span> <span class="literal string single">'world'</span><span class="punctuation">,</span> <span class="literal string single">'am'</span><span class="punctuation">,</span> <span class="literal string single">'he'</span><span class="punctuation">]</span> <span class="operator">*</span> <span class="name">N</span><span class="punctuation">))</span>
 </pre>
 <div class="section" id="id14">
-<h2><a class="toc-backref" href="#id43">局部变量</a></h2>
+<h2><a class="toc-backref" href="#id49">局部变量</a></h2>
 <p>在函数之内。函数执行结束，局部变量消失。</p>
 </div>
 <div class="section" id="id15">
-<h2><a class="toc-backref" href="#id44">全局变量</a></h2>
+<h2><a class="toc-backref" href="#id50">全局变量</a></h2>
 <p>全局变量位于函数之外，模块之内。全局变量对所有模块内的函数可见（可读）。如果在函数内要对全局变量重新赋值，那么要先用 <tt class="docutils literal">global</tt> 声明之 （declare）。</p>
 <pre class="code python literal-block">
 <span class="name">verbose</span> <span class="operator">=</span> <span class="name builtin pseudo">True</span>
@@ -1313,7 +1325,7 @@ error-prone（易错）</p>
 <p>练习： 定义一个函数 <tt class="docutils literal">empty_dict</tt> 清空字典 <tt class="docutils literal">record</tt>。 要求: 不能用 <tt class="docutils literal">return</tt> 语句。 提示： 可以用 <tt class="docutils literal">pop</tt> 方法， 或者直接给 <tt class="docutils literal">record</tt> 赋值 <tt class="docutils literal">{}</tt> 。</p>
 </div>
 <div class="section" id="id16">
-<h2><a class="toc-backref" href="#id45">调用函数与传递参数</a></h2>
+<h2><a class="toc-backref" href="#id51">调用函数与传递参数</a></h2>
 <p>在使用函数前要先确定函数已经被定义。</p>
 <p>区别 <tt class="docutils literal">argument</tt> 与 <tt class="docutils literal">parameter</tt> 。传过去的是 <tt class="docutils literal">argument</tt> ， 函数头的参数列表是 <tt class="docutils literal">parameter</tt> 。 <tt class="docutils literal">argument</tt> 的值赋给 <tt class="docutils literal">parameter</tt> ， <tt class="docutils literal">parameter</tt> 是函数的局部变量。</p>
 <p><tt class="docutils literal">argument</tt> 与 <tt class="docutils literal">parameter</tt> 的名字可以相同也可以不同。</p>
@@ -1334,13 +1346,253 @@ error-prone（易错）</p>
 <p>以上 t 一个是全局变量一个是局部变量。</p>
 </div>
 <div class="section" id="flow-of-execution">
-<h2><a class="toc-backref" href="#id46">函数执行顺序 （flow of execution）</a></h2>
+<h2><a class="toc-backref" href="#id52">函数执行顺序 （flow of execution）</a></h2>
 <p>函数的定义不执行，被调用时才执行。</p>
 <p>顺序执行。 当遇到函数调用时，跳转到函数，执行函数，函数返回后继续执行跳转地后一条语句。</p>
 </div>
 </div>
 <div class="section" id="id17">
-<h1><a class="toc-backref" href="#id47">参考</a></h1>
+<h1><a class="toc-backref" href="#id53">排序</a></h1>
+<p>排序是常见重要的操作。 按照成绩排序。  按照文件名排序。  按照文件大小排序。  按照时间排序。</p>
+<p>Python自带的 <tt class="docutils literal">sorted</tt> 可以很好满足排序需求。</p>
+<div class="section" id="id18">
+<h2><a class="toc-backref" href="#id54">排序一组数或一组字符串</a></h2>
+<p>如果需要从大到小排序， 添加 <tt class="docutils literal">reverse=True</tt> 。</p>
+<pre class="code python literal-block">
+<span class="comment single"># Sort numbers</span>
+<span class="keyword namespace">import</span> <span class="name namespace">random</span>
+<span class="name">a</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">100</span><span class="punctuation">)</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">5</span><span class="punctuation">)]</span> <span class="comment single"># a list of 5 random numbers between 0 and 100</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+
+<span class="name">sa_incr</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">sa_incr</span><span class="punctuation">)</span>
+
+<span class="name">sa_decr</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">,</span> <span class="name">reverse</span><span class="operator">=</span><span class="name builtin pseudo">True</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">sa_decr</span><span class="punctuation">)</span>
+
+<span class="comment single"># Sort a list of strings</span>
+<span class="name">s</span> <span class="operator">=</span> <span class="literal string single">'D3.js is a JavaScript library for manipulating documents based on data. D3 helps you bring data to life using HTML, SVG, and CSS. D3’s emphasis on web standards gives you the full capabilities of modern browsers without tying yourself to a proprietary framework, combining powerful visualization components and a data-driven approach to DOM manipulation.  https://d3js.org/'</span>
+<span class="name">lst</span> <span class="operator">=</span> <span class="name builtin">list</span><span class="punctuation">(</span><span class="name builtin">set</span><span class="punctuation">(</span><span class="name">s</span><span class="operator">.</span><span class="name">split</span><span class="punctuation">()))</span>
+
+<span class="name">sa_incr</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">sa_incr</span><span class="punctuation">)</span>
+
+<span class="name">sa_decr</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">reverse</span><span class="operator">=</span><span class="name builtin pseudo">True</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">sa_decr</span><span class="punctuation">)</span>
+</pre>
+</div>
+<div class="section" id="id19">
+<h2><a class="toc-backref" href="#id55">自定义排序算法</a></h2>
+<p>为了弄清排序的原理， 我们看两种排序算法。</p>
+<div class="section" id="id20">
+<h3><a class="toc-backref" href="#id56">选择排序</a></h3>
+<p>遍历列表，每次把最小的那个放到最左边位置。</p>
+<pre class="code python literal-block">
+<span class="keyword">def</span> <span class="name function">swap</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">,</span> <span class="name">i</span><span class="punctuation">,</span> <span class="name">j</span><span class="punctuation">):</span>
+    <span class="name">L</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">],</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">],</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">]</span>
+
+
+<span class="keyword">def</span> <span class="name function">selection_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">):</span>
+    <span class="name">i</span> <span class="operator">=</span> <span class="literal number integer">0</span>
+    <span class="keyword">while</span> <span class="name">i</span> <span class="operator">&lt;</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">):</span>
+        <span class="name">min_val</span> <span class="operator">=</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span>
+        <span class="name">k</span> <span class="operator">=</span> <span class="name">j</span> <span class="operator">=</span> <span class="name">i</span>
+        <span class="keyword">while</span> <span class="name">j</span> <span class="operator">&lt;</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">):</span>
+            <span class="keyword">if</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">]</span> <span class="operator">&lt;</span> <span class="name">min_val</span><span class="punctuation">:</span>
+                <span class="name">min_val</span> <span class="operator">=</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">]</span>
+                <span class="name">k</span> <span class="operator">=</span> <span class="name">j</span>
+            <span class="name">j</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+        <span class="name">swap</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">,</span> <span class="name">i</span><span class="punctuation">,</span> <span class="name">k</span><span class="punctuation">)</span> <span class="comment single"># will change L</span>
+        <span class="name">i</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+    <span class="keyword">return</span> <span class="name">L</span>
+
+<span class="keyword">if</span> <span class="name variable magic">__name__</span> <span class="operator">==</span> <span class="literal string single">'__main__'</span><span class="punctuation">:</span>
+
+    <span class="keyword namespace">import</span> <span class="name namespace">random</span>
+    <span class="keyword">for</span> <span class="name">n</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">10</span><span class="punctuation">):</span>
+        <span class="name">a</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">100</span><span class="punctuation">)</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">)]</span>
+        <span class="name">sa</span> <span class="operator">=</span> <span class="name">selection_sort</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+        <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sa</span><span class="punctuation">)</span>
+        <span class="keyword">assert</span> <span class="name">sa</span> <span class="operator">==</span> <span class="name">a</span>
+        <span class="keyword">assert</span> <span class="name">sa</span> <span class="operator">==</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+</pre>
+</div>
+<div class="section" id="merge-sort">
+<h3><a class="toc-backref" href="#id57">合并排序 （Merge sort）</a></h3>
+<p>将列表一分为二，对每半部分排序，把排好序的两部分合并之（确保合并后同样是排好序的）。 注意到，以下的实现方式是递归。</p>
+<pre class="code python literal-block">
+<span class="keyword">def</span> <span class="name function">_merge</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">,</span> <span class="name">R</span><span class="punctuation">):</span>
+    <span class="literal string doc">''' Return a sorted list that combines the sorted list L and sorted list R.'''</span>
+    <span class="name">nL</span> <span class="operator">=</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span>
+    <span class="name">nR</span> <span class="operator">=</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">R</span><span class="punctuation">)</span>
+    <span class="name">result</span> <span class="operator">=</span> <span class="punctuation">[]</span>
+    <span class="name">i</span> <span class="operator">=</span> <span class="name">j</span> <span class="operator">=</span> <span class="name">count</span> <span class="operator">=</span> <span class="literal number integer">0</span>
+    <span class="keyword">while</span> <span class="name">count</span> <span class="operator">&lt;</span> <span class="name">nL</span> <span class="operator">+</span> <span class="name">nR</span><span class="punctuation">:</span>
+        <span class="keyword">if</span> <span class="name">i</span> <span class="operator">&gt;=</span> <span class="name">nL</span> <span class="operator word">and</span> <span class="name">j</span> <span class="operator">&lt;</span> <span class="name">nR</span><span class="punctuation">:</span>
+            <span class="name">result</span><span class="operator">.</span><span class="name">append</span><span class="punctuation">(</span><span class="name">R</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">])</span>
+            <span class="name">j</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+        <span class="keyword">elif</span> <span class="name">j</span> <span class="operator">&gt;=</span> <span class="name">nR</span> <span class="operator word">and</span> <span class="name">i</span> <span class="operator">&lt;</span> <span class="name">nL</span><span class="punctuation">:</span>
+            <span class="name">result</span><span class="operator">.</span><span class="name">append</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">])</span>
+            <span class="name">i</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+        <span class="keyword">elif</span> <span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span> <span class="operator">&lt;</span> <span class="name">R</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">]:</span>
+            <span class="name">result</span><span class="operator">.</span><span class="name">append</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">])</span>
+            <span class="name">i</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+        <span class="keyword">else</span><span class="punctuation">:</span>
+            <span class="name">result</span><span class="operator">.</span><span class="name">append</span><span class="punctuation">(</span><span class="name">R</span><span class="punctuation">[</span><span class="name">j</span><span class="punctuation">])</span>
+            <span class="name">j</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+        <span class="name">count</span> <span class="operator">+=</span> <span class="literal number integer">1</span>
+    <span class="keyword">return</span> <span class="name">result</span>
+
+
+<span class="keyword">def</span> <span class="name function">merge_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">):</span>
+    <span class="keyword">if</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span> <span class="operator">&lt;=</span> <span class="literal number integer">1</span><span class="punctuation">:</span>
+        <span class="keyword">return</span> <span class="name">L</span>
+    <span class="keyword">else</span><span class="punctuation">:</span>
+        <span class="name">i</span> <span class="operator">=</span> <span class="name builtin">int</span><span class="punctuation">(</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span><span class="operator">/</span><span class="literal number integer">2</span><span class="punctuation">)</span>
+        <span class="name">l</span> <span class="operator">=</span> <span class="name">merge_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">[:</span><span class="name">i</span><span class="punctuation">])</span>
+        <span class="name">r</span> <span class="operator">=</span> <span class="name">merge_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">:])</span>
+        <span class="keyword">return</span> <span class="name">_merge</span><span class="punctuation">(</span><span class="name">l</span><span class="punctuation">,</span> <span class="name">r</span><span class="punctuation">)</span>
+
+<span class="keyword">if</span> <span class="name variable magic">__name__</span> <span class="operator">==</span> <span class="literal string single">'__main__'</span><span class="punctuation">:</span>
+
+    <span class="keyword namespace">import</span> <span class="name namespace">random</span>
+    <span class="keyword">for</span> <span class="name">n</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">100</span><span class="punctuation">):</span>
+        <span class="name">a</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">100</span><span class="punctuation">)</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">)]</span>
+        <span class="name">sa</span> <span class="operator">=</span> <span class="name">merge_sort</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+        <span class="keyword">assert</span> <span class="name">sa</span> <span class="operator">==</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">)</span>
+</pre>
+</div>
+</div>
+<div class="section" id="id21">
+<h2><a class="toc-backref" href="#id58">比较排序速度</a></h2>
+<p>排序是 Python 的核心算法，所以是优化了再优化。</p>
+<p>Python 自带的排序算法最快， <tt class="docutils literal">selection_sort</tt> 最慢。</p>
+<pre class="code python literal-block">
+<span class="keyword namespace">from</span> <span class="name namespace">merge_sort</span> <span class="keyword namespace">import</span> <span class="name">merge_sort</span>
+<span class="keyword namespace">from</span> <span class="name namespace">selection_sort</span> <span class="keyword namespace">import</span> <span class="name">selection_sort</span>
+
+<span class="keyword namespace">import</span> <span class="name namespace">random</span><span class="operator">,</span> <span class="name namespace">time</span>
+<span class="name">L</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">10000</span><span class="punctuation">)</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">10000</span><span class="punctuation">)]</span>
+
+<span class="keyword">print</span><span class="punctuation">(</span><span class="literal string single">'Python sort ...'</span><span class="punctuation">)</span>
+<span class="name">now</span> <span class="operator">=</span> <span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span>
+<span class="name">result0</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span> <span class="operator">-</span> <span class="name">now</span><span class="punctuation">)</span>
+
+
+<span class="keyword">print</span><span class="punctuation">(</span><span class="literal string single">'Merge sort ...'</span><span class="punctuation">)</span>
+<span class="name">now</span> <span class="operator">=</span> <span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span>
+<span class="name">result1</span> <span class="operator">=</span> <span class="name">merge_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span> <span class="operator">-</span> <span class="name">now</span><span class="punctuation">)</span>
+
+<span class="keyword">print</span><span class="punctuation">(</span><span class="literal string single">'Selection sort ...'</span><span class="punctuation">)</span>
+<span class="name">now</span> <span class="operator">=</span> <span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span>
+<span class="name">result2</span> <span class="operator">=</span> <span class="name">selection_sort</span><span class="punctuation">(</span><span class="name">L</span><span class="punctuation">)</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="name">time</span><span class="operator">.</span><span class="name">time</span><span class="punctuation">()</span> <span class="operator">-</span> <span class="name">now</span><span class="punctuation">)</span>
+
+<span class="keyword">assert</span> <span class="name">result0</span><span class="operator">==</span> <span class="name">result1</span>
+<span class="keyword">assert</span> <span class="name">result1</span> <span class="operator">==</span> <span class="name">result2</span>
+</pre>
+<p>在命令行运行上面的程序，在作者的计算机上得到如下的结果。</p>
+<div class="line-block">
+<div class="line">Python sort ...</div>
+<div class="line">0.002</div>
+<div class="line">Merge sort ...</div>
+<div class="line">0.083</div>
+<div class="line">Selection sort ...</div>
+<div class="line">11.57</div>
+</div>
+</div>
+<div class="section" id="id22">
+<h2><a class="toc-backref" href="#id59">排序元组列表</a></h2>
+<p>一个元组由多个元素组成，多个元组组成元组列表， 如何按照某个元素进行排序呢？</p>
+<p>可以有以下两种方案。一种用模块 <tt class="docutils literal">operator</tt> ， 一种用 <tt class="docutils literal">lambda</tt> 函数。</p>
+<pre class="code python literal-block">
+<span class="keyword">def</span> <span class="name function">sort_by_nth_element</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">n</span><span class="punctuation">):</span>
+    <span class="literal string doc">''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''</span>
+    <span class="keyword namespace">import</span> <span class="name namespace">operator</span>
+    <span class="name">result</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="name">operator</span><span class="operator">.</span><span class="name">itemgetter</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">))</span>
+    <span class="keyword">return</span> <span class="name">result</span>
+
+
+<span class="keyword">def</span> <span class="name function">sort_by_nth_element2</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">n</span><span class="punctuation">):</span>
+    <span class="literal string doc">''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''</span>
+    <span class="keyword namespace">import</span> <span class="name namespace">operator</span>
+    <span class="name">result</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="keyword">lambda</span> <span class="name">x</span><span class="punctuation">:</span> <span class="name">x</span><span class="punctuation">[</span><span class="name">n</span><span class="punctuation">])</span> <span class="comment single"># https://stackoverflow.com/questions/8966538/syntax-behind-sortedkey-lambda</span>
+    <span class="keyword">return</span> <span class="name">result</span>
+
+
+<span class="keyword">if</span> <span class="name variable magic">__name__</span> <span class="operator">==</span> <span class="literal string single">'__main__'</span><span class="punctuation">:</span>
+    <span class="name">lst</span> <span class="operator">=</span> <span class="punctuation">[(</span><span class="literal number integer">1</span><span class="punctuation">,</span> <span class="literal string single">'xxx'</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">),</span> <span class="punctuation">(</span><span class="literal number integer">2</span><span class="punctuation">,</span> <span class="literal string single">'aaa'</span><span class="punctuation">,</span> <span class="literal number integer">1</span><span class="punctuation">)]</span>
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">0</span><span class="punctuation">))</span>
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">1</span><span class="punctuation">))</span>
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">))</span>
+
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element2</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">0</span><span class="punctuation">))</span>
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element2</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">1</span><span class="punctuation">))</span>
+    <span class="keyword">print</span><span class="punctuation">(</span><span class="name">sort_by_nth_element2</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">))</span>
+</pre>
+</div>
+<div class="section" id="lambda">
+<h2><a class="toc-backref" href="#id60">巧用 lambda 函数进行灵活排序</a></h2>
+<p>如何把一个由字符串组成的列表按照字符串的长短进行排序？</p>
+<pre class="code python literal-block">
+<span class="name">lst</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="literal string single">'this'</span><span class="punctuation">,</span> <span class="literal string single">'is'</span><span class="punctuation">,</span> <span class="literal string single">'a'</span><span class="punctuation">,</span> <span class="literal string single">'example'</span><span class="punctuation">]</span>
+<span class="name">a</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="keyword">lambda</span> <span class="name">x</span><span class="punctuation">:</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">x</span><span class="punctuation">))</span>
+<span class="name">b</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="keyword">lambda</span> <span class="name">x</span><span class="punctuation">:</span> <span class="operator">-</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">x</span><span class="punctuation">))</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="literal string single">'</span><span class="literal string escape">\n</span><span class="literal string single">'</span><span class="operator">.</span><span class="name">join</span><span class="punctuation">(</span><span class="name">a</span><span class="punctuation">))</span>
+
+<span class="name">s</span> <span class="operator">=</span> <span class="literal string single">'''https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596
+Romeo and Juliet
+PROLOGUE
+Two households, both alike in dignity,
+In fair Verona, where we lay our scene,
+From ancient grudge break to new mutiny,
+Where civil blood makes civil hands unclean.
+From forth the fatal loins of these two foes
+A pair of star-cross'd lovers take their life;
+Whose misadventured piteous overthrows
+Doth with their death bury their parents' strife.
+The fearful passage of their death-mark'd love,
+And the continuance of their parents' rage,
+Which, but their children's end, nought could remove,
+Is now the two hours' traffic of our stage;
+The which if you with patient ears attend,
+What here shall miss, our toil shall strive to mend.'''</span>
+
+<span class="name">lst</span> <span class="operator">=</span> <span class="name">s</span><span class="operator">.</span><span class="name">split</span><span class="punctuation">(</span><span class="literal string single">'</span><span class="literal string escape">\n</span><span class="literal string single">'</span><span class="punctuation">)</span>
+<span class="name">c</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="keyword">lambda</span> <span class="name">x</span><span class="punctuation">:</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">x</span><span class="punctuation">))</span>
+<span class="name">d</span> <span class="operator">=</span> <span class="name builtin">sorted</span><span class="punctuation">(</span><span class="name">lst</span><span class="punctuation">,</span> <span class="name">key</span><span class="operator">=</span><span class="keyword">lambda</span> <span class="name">x</span><span class="punctuation">:</span> <span class="operator">-</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">x</span><span class="punctuation">))</span>
+<span class="keyword">print</span><span class="punctuation">(</span><span class="literal string single">'</span><span class="literal string escape">\n</span><span class="literal string single">'</span><span class="operator">.</span><span class="name">join</span><span class="punctuation">(</span><span class="name">c</span><span class="punctuation">))</span>
+</pre>
+<p>以上程序运行会输出如下结果。</p>
+<div class="line-block">
+<div class="line">a</div>
+<div class="line">is</div>
+<div class="line">this</div>
+<div class="line">example</div>
+<div class="line">PROLOGUE</div>
+<div class="line">Romeo and Juliet</div>
+<div class="line">Two households, both alike in dignity,</div>
+<div class="line">Whose misadventured piteous overthrows</div>
+<div class="line">In fair Verona, where we lay our scene,</div>
+<div class="line">From ancient grudge break to new mutiny,</div>
+<div class="line">The which if you with patient ears attend,</div>
+<div class="line">And the continuance of their parents' rage,</div>
+<div class="line">Is now the two hours' traffic of our stage;</div>
+<div class="line">Where civil blood makes civil hands unclean.</div>
+<div class="line">From forth the fatal loins of these two foes</div>
+<div class="line">A pair of star-cross'd lovers take their life;</div>
+<div class="line">The fearful passage of their death-mark'd love,</div>
+<div class="line">Doth with their death bury their parents' strife.</div>
+<div class="line">What here shall miss, our toil shall strive to mend.</div>
+<div class="line">Which, but their children's end, nought could remove,</div>
+<div class="line"><a class="reference external" href="https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596">https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596</a></div>
+</div>
+</div>
+</div>
+<div class="section" id="id23">
+<h1><a class="toc-backref" href="#id61">参考</a></h1>
 <ul class="simple">
 <li>Think Python 2e – Green Tea Press.  <a class="reference external" href="http://greenteapress.com/thinkpython2/thinkpython2.pdf">http://greenteapress.com/thinkpython2/thinkpython2.pdf</a>.</li>
 </ul>
diff --git a/LectureNotesOnPython.rst b/LectureNotesOnPython.rst
index 5251078..a729f22 100644
--- a/LectureNotesOnPython.rst
+++ b/LectureNotesOnPython.rst
@@ -5,7 +5,7 @@ Lecture Notes on Python
 :Authors:
    蓝珲 (lanhui AT zjnu.edu.cn)
 
-:Version: 0.1.1 of 2019-04-14
+:Version: 0.1.2 of 2019-04-14
 
 	  
 
@@ -1071,6 +1071,277 @@ key与value互换
 
 
 
+排序
+------------------------------------------------
+
+排序是常见重要的操作。 按照成绩排序。  按照文件名排序。  按照文件大小排序。  按照时间排序。
+
+Python自带的 ``sorted`` 可以很好满足排序需求。
+
+
+排序一组数或一组字符串
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+如果需要从大到小排序， 添加 ``reverse=True`` 。
+
+.. code:: python
+
+         # Sort numbers
+         import random
+         a = [random.randint(0,100) for i in range(5)] # a list of 5 random numbers between 0 and 100
+         print(a)
+         
+         sa_incr = sorted(a)
+         print(sa_incr)
+         
+         sa_decr = sorted(a, reverse=True)
+         print(sa_decr)
+         
+         # Sort a list of strings
+         s = 'D3.js is a JavaScript library for manipulating documents based on data. D3 helps you bring data to life using HTML, SVG, and CSS. D3’s emphasis on web standards gives you the full capabilities of modern browsers without tying yourself to a proprietary framework, combining powerful visualization components and a data-driven approach to DOM manipulation.  https://d3js.org/'
+         lst = list(set(s.split()))
+         
+         sa_incr = sorted(lst)
+         print(sa_incr)
+         
+         sa_decr = sorted(lst, reverse=True)
+         print(sa_decr)
+         
+
+自定义排序算法
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+为了弄清排序的原理， 我们看两种排序算法。
+
+
+选择排序
+```````````````````````````````````````````````````
+
+遍历列表，每次把最小的那个放到最左边位置。
+
+.. code:: python
+
+         def swap(L, i, j):
+             L[j], L[i] = L[i], L[j]
+         
+         
+         def selection_sort(L):
+             i = 0
+             while i < len(L):
+                 min_val = L[i]
+                 k = j = i
+                 while j < len(L):
+                     if L[j] < min_val:
+                         min_val = L[j]
+                         k = j
+                     j += 1
+                 swap(L, i, k) # will change L
+                 i += 1
+             return L
+         
+         if __name__ == '__main__':
+             
+             import random
+             for n in range(10):
+                 a = [random.randint(0,100) for i in range(n)]
+                 sa = selection_sort(a)
+                 print(sa)
+                 assert sa == a
+                 assert sa == sorted(a)
+         
+
+合并排序 （Merge sort）
+```````````````````````````````````````````````````
+
+将列表一分为二，对每半部分排序，把排好序的两部分合并之（确保合并后同样是排好序的）。 注意到，以下的实现方式是递归。
+
+.. code:: python
+
+         def _merge(L, R):
+             ''' Return a sorted list that combines the sorted list L and sorted list R.'''
+             nL = len(L)
+             nR = len(R)
+             result = []
+             i = j = count = 0
+             while count < nL + nR:
+                 if i >= nL and j < nR:
+                     result.append(R[j])
+                     j += 1
+                 elif j >= nR and i < nL:
+                     result.append(L[i])
+                     i += 1
+                 elif L[i] < R[j]:
+                     result.append(L[i])
+                     i += 1
+                 else:
+                     result.append(R[j])
+                     j += 1
+                 count += 1
+             return result
+         
+         
+         def merge_sort(L):
+             if len(L) <= 1:
+                 return L
+             else:
+                 i = int(len(L)/2)
+                 l = merge_sort(L[:i])
+                 r = merge_sort(L[i:])
+                 return _merge(l, r)
+         
+         if __name__ == '__main__':
+                 
+             import random
+             for n in range(100):
+                 a = [random.randint(0,100) for i in range(n)]
+                 sa = merge_sort(a)
+                 assert sa == sorted(a)
+         
+
+
+比较排序速度
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+排序是 Python 的核心算法，所以是优化了再优化。
+
+Python 自带的排序算法最快， ``selection_sort`` 最慢。 
+
+
+.. code:: python
+
+         from merge_sort import merge_sort
+         from selection_sort import selection_sort
+         
+         import random, time
+         L = [random.randint(0,10000) for i in range(10000)]
+         
+         print('Python sort ...')
+         now = time.time()
+         result0 = sorted(L)
+         print(time.time() - now)
+         
+         
+         print('Merge sort ...')
+         now = time.time()
+         result1 = merge_sort(L)
+         print(time.time() - now)
+         
+         print('Selection sort ...')
+         now = time.time()
+         result2 = selection_sort(L)
+         print(time.time() - now)
+         
+         assert result0== result1
+         assert result1 == result2
+         
+
+在命令行运行上面的程序，在作者的计算机上得到如下的结果。
+
+| Python sort ...
+| 0.002
+| Merge sort ...
+| 0.083
+| Selection sort ...
+| 11.57
+
+
+排序元组列表
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+一个元组由多个元素组成，多个元组组成元组列表， 如何按照某个元素进行排序呢？
+
+可以有以下两种方案。一种用模块 ``operator`` ， 一种用 ``lambda`` 函数。
+
+.. code:: python
+
+         def sort_by_nth_element(lst, n):
+             ''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''
+             import operator
+             result = sorted(lst, key=operator.itemgetter(n))    
+             return result
+         
+         
+         def sort_by_nth_element2(lst, n):
+             ''' Return a sorted list of tuples lst, according to the nth element in each tuple.'''
+             import operator
+             result = sorted(lst, key=lambda x: x[n]) # https://stackoverflow.com/questions/8966538/syntax-behind-sortedkey-lambda
+             return result
+         
+         
+         if __name__ == '__main__':
+             lst = [(1, 'xxx', 2), (2, 'aaa', 1)]
+             print(sort_by_nth_element(lst, 0))
+             print(sort_by_nth_element(lst, 1))    
+             print(sort_by_nth_element(lst, 2))
+             
+             print(sort_by_nth_element2(lst, 0))
+             print(sort_by_nth_element2(lst, 1))    
+             print(sort_by_nth_element2(lst, 2))
+         
+
+巧用 lambda 函数进行灵活排序
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+如何把一个由字符串组成的列表按照字符串的长短进行排序？
+
+.. code:: python
+
+         lst = ['this', 'is', 'a', 'example']
+         a = sorted(lst, key=lambda x: len(x))
+         b = sorted(lst, key=lambda x: -len(x))
+         print('\n'.join(a))
+         
+         s = '''https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596
+         Romeo and Juliet
+         PROLOGUE
+         Two households, both alike in dignity,
+         In fair Verona, where we lay our scene,
+         From ancient grudge break to new mutiny,
+         Where civil blood makes civil hands unclean.
+         From forth the fatal loins of these two foes
+         A pair of star-cross'd lovers take their life;
+         Whose misadventured piteous overthrows
+         Doth with their death bury their parents' strife.
+         The fearful passage of their death-mark'd love,
+         And the continuance of their parents' rage,
+         Which, but their children's end, nought could remove,
+         Is now the two hours' traffic of our stage;
+         The which if you with patient ears attend,
+         What here shall miss, our toil shall strive to mend.'''
+         
+         lst = s.split('\n')
+         c = sorted(lst, key=lambda x: len(x))
+         d = sorted(lst, key=lambda x: -len(x))
+         print('\n'.join(c))
+
+
+以上程序运行会输出如下结果。
+
+
+| a
+| is
+| this
+| example
+| PROLOGUE
+| Romeo and Juliet
+| Two households, both alike in dignity,
+| Whose misadventured piteous overthrows
+| In fair Verona, where we lay our scene,
+| From ancient grudge break to new mutiny,
+| The which if you with patient ears attend,
+| And the continuance of their parents' rage,
+| Is now the two hours' traffic of our stage;
+| Where civil blood makes civil hands unclean.
+| From forth the fatal loins of these two foes
+| A pair of star-cross'd lovers take their life;
+| The fearful passage of their death-mark'd love,
+| Doth with their death bury their parents' strife.
+| What here shall miss, our toil shall strive to mend.
+| Which, but their children's end, nought could remove,
+| https://genius.com/William-shakespeare-romeo-and-juliet-act-1-prologue-annotated#note-2756596
+
+
+
 参考
 ------