diff options
Diffstat (limited to 'LectureNotesOnPython.rst')
| -rw-r--r-- | LectureNotesOnPython.rst | 273 |
1 files changed, 272 insertions, 1 deletions
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 + + + 参考 ------ |