排序
排序是指将集合中的元素按某种顺序排列的过程。比如，一个单词列表可以按字母表或长度排序；一个城市列表可以按人口、面积或邮编排序。我们已经探讨过一些利用有序列表提高效率的算法（比如异序词的例子，以及二分搜索算法）。
排序算法有很多，对它们的分析也已经很透彻了。这说明，排序是计算机科学中的一个重要的研究领域。给大量元素排序可能消耗大量的计算资源。与搜索算法类似，排序算法的效率与待处理元素的数目相关。对于小型集合，采用复杂的排序算法可能得不偿失；对于大型集合，需要尽可能充分地利用各种改善措施。本节将讨论多种排序技巧，并比较它们的运行时间。
在讨论具体的算法之前，先思考如何分析排序过程。首先，排序算法要能比较大小。为了给一个集合排序，需要某种系统化的比较方法，以检查元素的排列是否违反了顺序。在衡量排序过程时，最常用的指标就是总的比较次数。其次，当元素的排列顺序不正确时，需要交换它们的位置。交换是一个耗时的操作，总的交换次数对于衡量排序算法的总体效率来说也很重要。
冒泡排序
冒泡排序 多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。本质上，每个元素通过 “冒泡” 找到自己所属的位置。
图5-13 展示了冒泡排序的第一轮遍历过程。深色的是正在比较的元素。如果列表中有 n 个元素，那么第一轮遍历要比较 n-1 对。注意，最大的元素会一直往前挪，直到遍历过程结束。
第二轮遍历开始时，最大值已经在正确位置上了。还剩 n-1 个元素需要排列，也就是说要比较 n-2 对。既然每一轮都将下一个最大的元素放到正确位置上，那么需要遍历的轮数就是 n-1。完成 n-1 轮后，最小的元素必然在正确位置上，因此不必再做处理。代码清单5-9 给出了完整的 bubbleSort 函数。该函数以一个列表为参数，必要时会交换其中的元素。
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)Python 中的交换操作和其他大部分编程语言中的略有不同。在交换两个元素的位置时，通常需要一个临时存储位置（额外的内存位置）。以下代码片段交换列表中的第 i 个和第 j 个元素的位置。如果没有临时存储位置，其中一个值就会被覆盖。
temp = alist[i]
alist[i] = alist[j]
alist[j] = tempPython 允许同时赋值。执行语句 a, b = b, a，相当于同时执行两条赋值语句，如图5-14 所示。利用 Python 的这一特性，就可以用一条语句完成交换操作。
在代码清单5-9 中，第5～7行采用3步法交换第 i 个和第 i+1 个元素的位置。注意，也可以通过同时赋值来实现。
在分析冒泡排序算法时要注意，不管一开始元素是如何排列的，给含有 n 个元素的列表排序总需要遍历 n-1 轮。表5-6 展示了每一轮的比较次数。总的比较次数是前 n-1 个整数之和。由于前 n 个整数之和是 \$1/2n^2+1/2n\$，因此前 n-1 个整数之和就是 \$1/2n^2+1/2n-n\$，即 \$1/2n^2-1/2n\$。这表明，该算法的时间复杂度是 \$O(n^2)\$。在最好情况下，列表已经是有序的，不需要执行交换操作。在最坏情况下，每一次比较都将导致一次交换。
冒泡排序通常被认为是效率最低的排序算法，因为在确定最终的位置前必须交换元素。“多余” 的交换操作代价很大。不过，由于冒泡排序要遍历列表中未排序的部分，因此它具有其他排序算法没有的用途。特别是，如果在一轮遍历中没有发生元素交换，就可以确定列表已经有序。可以修改冒泡排序函数，使其在遇到这种情况时提前终止。对于只需要遍历几次的列表，冒泡排序可能有优势，因为它能判断出有序列表并终止排序过程。代码清单5-10 实现了如上所述的修改，这种排序通常被称作短冒泡。
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum = passnum-1
alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)选择排序
选择排序 在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。要实现这一点，选择排序在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。和冒泡排序一样，第一次遍历后，最大的元素就位；第二次遍历后，第二大的元素就位，依此类推。若给 n 个元素排序，需要遍历 n-1 轮，这是因为最后一个元素要到 n-1 轮遍历后才就位。
图5-15展示了完整的选择排序过程。每一轮遍历都选择待排序元素中最大的元素，并将其放到正确位置上。第一轮放好 93，第二轮放好 77，第三轮放好 55，依此类推。代码清单5-11 给出了选择排序函数。
def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)可以看出，选择排序算法和冒泡排序算法的比较次数相同，所以时间复杂度也是 \$O(n^2)\$。但是，由于减少了交换次数，因此选择排序算法通常更快。就本节的列表示例而言，冒泡排序交换了 20 次，而选择排序只需交换 8 次。
插入排序
插入排序 的时间复杂度也是 \$O(n^2)\$，但原理稍有不同。它在列表较低的一端维护一个有序的子列表，并逐个将每个新元素 “插入” 这个子列表。图5-16 展示了插入排序的过程。深色元素代表有序子列表中的元素。
首先假设位置 0 处的元素是只含单个元素的有序子列表。从元素 1 到元素 n-1，每一轮都将当前元素与有序子列表中的元素进行比较。在有序子列表中，将比它大的元素右移；当遇到一个比它小的元素或抵达子列表终点时，就可以插入当前元素。
图5-17 详细展示了第5轮遍历的情况。此刻，有序子列表包含 5 个元素：17、26、54、77 和 93。现在想插入 31。第一次与 93 比较，结果是将 93 向右移；同理，77 和 54 也向右移。遇到 26 时，就不移了，并且 31 找到了正确位置。现在，有序子列表有 6 个元素。
从代码清单5-12 可知，在给 n 个元素排序时，插入排序算法需要遍历 n-1 轮。循环从位置 1 开始，直到位置 n-1 结束，这些元素都需要被插入到有序子列表中。第 8 行实现了移动操作，将列表中的一个值挪一个位置，为待插入元素腾出空间。要记住，这不是之前的算法进行的那种完整的交换操作。
def insertionSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)在最坏情况下，插入排序算法的比较次数是前 n-1 个整数之和，对应的时间复杂度是 \$O(n^2)\$。在最好情况下（列表已经是有序的），每一轮只需比较一次。
移动操作和交换操作有一个重要的不同点。总体来说，交换操作的处理时间大约是移动操作的 3 倍，因为后者只需进行一次赋值。在基准测试中，插入排序算法的性能很不错。
希尔排序
希尔排序 也称 “递减增量排序”，它对插入排序做了改进，将列表分成数个子列表，并对每一个子列表应用插入排序。如何切分列表是希尔排序的关键——并不是连续切分，而是使用增量 i（有时称作步长）选取所有间隔为 i 的元素组成子列表。以图5-18 中的列表为例，这个列表有 9 个元素。如果增量为 3，就有 3 个子列表，每个都可以应用插入排序，结果如图5-19 所示。尽管列表仍然不算完全有序，但通过给子列表排序，我们已经让元素离它们的最终位置更近了。
图5-20 展示了最终的插入排序过程。由于有了之前的子列表排序，因此总移动次数已经减少了。本例只需要再移动 4 次。
如前所述，如何切分列表是希尔排序的关键。代码清单5-13 中的函数采用了另一组增量。先为 n/2 个子列表排序，接着是 n/4 个子列表。最终，整个列表由基本的插入排序算法排好序。图5-21 展示了采用这种增量后的第一批子列表。
def shellSort(alist):
sublistcount = len(alist)//2
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)
print("After increments of size",sublistcount,
"The list is",alist)
sublistcount = sublistcount // 2
def gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):
currentvalue = alist[i]
position = i
while position>=gap and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position = position-gap
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)下面对 shellSort 的调用示例给出了使用每个增量之后的结果（部分有序），以及增量为 1 的插入排序结果。
>>> alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
>>> shellSort(alist)
After increments of size 4 the list is
[20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 the list is
[20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 the list is
[17, 20, 26, 31, 44, 54, 55, 77, 93]乍看之下，你可能会觉得希尔排序不可能比插入排序好，因为最后一步要做一次完整的插入排序。但实际上，列表已经由增量的插入排序做了预处理，所以最后一步插入排序不需要进行多次比较或移动。也就是说，每一轮遍历都生成了“更有序”的列表，这使得最后一步非常高效。
尽管对希尔排序的总体分析已经超出了本书的讨论范围，但是不妨了解一下它的时间复杂度。基于上述行为，希尔排序的时间复杂度大概介于 \$O(n)\$ 和 \$O(n^2)\$ 之间。若采用代码清单5-13 中的增量，则时间复杂度是 \$O(n^2)\$。通过改变增量，比如采用 2k-1（1, 3, 7, 15, 31, …），希尔排序的时间复杂度可以达到 \$O(n^(3/2))\$。
归并排序
现在，我们将注意力转向使用分治策略改进排序算法。要研究的第一个算法是归并排序，它是递归算法，每次将一个列表一分为二。如果列表为空或只有一个元素，那么从定义上来说它就是有序的（基本情况）。如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。当两部分都有序后，就进行归并这一基本操作。归并是指将两个较小的有序列表归并为一个有序列表的过程。图5-22a 展示了示例列表被拆分后的情况，图5-22b 给出了归并后的有序列表。
在代码清单5-14 中，mergeSort 函数以处理基本情况开始。如果列表的长度小于或等于 1，说明它已经是有序列表，因此不需要做额外的处理。如果长度大于 1，则通过 Python 的切片操作得到左半部分和右半部分。要注意，列表所含元素的个数可能不是偶数。这并没有关系，因为左右子列表的长度最多相差 1。
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] <= righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)在第 8～9 行对左右子列表调用 mergeSort 函数后，就假设它们已经排好序了。第 11～31 行负责将两个小的有序列表归并为一个大的有序列表。注意，归并操作每次从有序列表中取出最小值，放回初始列表（alist）。
mergeSort 函数有一条 print 语句（第 2 行），用于在每次调用开始时展示待排序列表的内容。第 32 行也有一条 print 语句，用于展示归并过程。以下脚本展示了针对示例列表执行 mergeSort 函数的结果。注意，列表 [44, 55, 20] 不会均分，第一部分是 [44]，第二部分是 [55, 20]。很容易看出，拆分操作最终生成了能立即与其他有序列表归并的列表。
>>> b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
>>> mergeSort(b)
Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting [54, 26, 93, 17]
Splitting [54, 26]
Splitting [54]
Merging [54]
Splitting [26]
Merging [26]
Merging [26, 54]
Splitting [93, 17]
Splitting [93]
Merging [93]
Splitting [17]
Merging [17]
Merging [17, 93]
Merging [17, 26, 54, 93]
Splitting [77, 31, 44, 55, 20]
Splitting [77, 31]
Splitting [77]
Merging [77]
Splitting [31]
Merging [31]
Merging [31, 77]
Splitting [44, 55, 20]
Splitting [44]
Merging [44]
Splitting [55, 20]
Splitting [55]
Merging [55]
Splitting [20]
Merging [20]
Merging [20, 55]
Merging [20, 44, 55]
Merging [20, 31, 44, 55, 77]
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
>>>分析 mergeSort 函数时，要考虑它的两个独立的构成部分。首先，列表被一分为二。在学习二分搜索时已经算过，当列表的长度为 n 时，能切分 \$log_2n\$ 次。第二个处理过程是归并。列表中的每个元素最终都得到处理，并被放到有序列表中。所以，得到长度为 n 的列表需要进行 n 次操作。由此可知，需要进行 \$logn\$ 次拆分，每一次需要进行 n 次操作，所以一共是 \$nlogn\$ 次操作。也就是说，归并排序算法的时间复杂度是 \$O(nlogn)\$。
你应该记得，切片操作的时间复杂度是 \$O(k)\$，其中 k 是切片的大小。为了保证 mergeSort 函数的时间复杂度是 \$O(nlogn)\$，需要去除切片运算符。在进行递归调用时，传入头和尾的下标即可做到这一点。我们将此留作练习。
有一点要注意：mergeSort 函数需要额外的空间来存储切片操作得到的两半部分。当列表较大时，使用额外的空间可能会使排序出现问题。
快速排序
和归并排序一样，快速排序也采用分治策略，但不使用额外的存储空间。不过，代价是列表可能不会被一分为二。出现这种情况时，算法的效率会有所下降。
快速排序算法首先选出一个 基准值。尽管有很多种选法，但为简单起见，本节选取列表中的第一个元素。基准值的作用是帮助切分列表。在最终的有序列表中，基准值的位置通常被称作分割点，算法在分割点切分列表，以进行对快速排序的子调用。
在图5-23 中，元素 54 将作为第一个基准值。从前面的例子可知，54 最终应该位于 31 当前所在的位置。下一步是分区操作。它会找到分割点，同时将其他元素放到正确的一边——要么大于基准值，要么小于基准值。
分区操作首先找到两个坐标——leftmark 和 rightmark——它们分别位于列表剩余元素的开头和末尾，如图5-24 所示。分区的目的是根据待排序元素与基准值的相对大小将它们放到正确的一边，同时逐渐逼近分割点。图5-24 展示了为元素 54 寻找正确位置的过程。
首先加大 leftmark，直到遇到一个大于基准值的元素。然后减小 rightmark，直到遇到一个小于基准值的元素。这样一来，就找到两个与最终的分割点错序的元素。本例中，这两个元素就是 93 和 20。互换这两个元素的位置，然后重复上述过程。
当 rightmark 小于 leftmark 时，过程终止。此时，rightmark 的位置就是分割点。将基准值与当前位于分割点的元素互换，即可使基准值位于正确位置，如图5-25 所示。分割点左边的所有元素都小于基准值，右边的所有元素都大于基准值。因此，可以在分割点处将列表一分为二，并针对左右两部分递归调用快速排序函数。
在代码清单5-15 中，快速排序函数 quickSort 调用了递归函数 quickSortHelper。quickSortHelper 首先处理和归并排序相同的基本情况。如果列表的长度小于或等于 1，说明它已经是有序列表；如果长度大于 1，则进行分区操作并递归地排序。分区函数 partition 实现了前面描述的过程。
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)在分析 quickSort 函数时要注意，对于长度为 n 的列表，如果分区操作总是发生在列表的中部，就会切分 \$logn\$ 次。为了找到分割点，n 个元素都要与基准值比较。所以，时间复杂度是 \$O(nlogn)\$。另外，快速排序算法不需要像归并排序算法那样使用额外的存储空间。
不幸的是，最坏情况下，分割点不在列表的中部，而是偏向某一端，这会导致切分不均匀。在这种情况下，含有 n 个元素的列表可能被分成一个不含元素的列表与一个含有 n-1 个元素的列表。然后，含有 n-1 个元素的列表可能会被分成不含元素的列表与一个含有 n-2 个元素的列表，依此类推。这会导致时间复杂度变为 \$O(n^2)\$，因为还要加上递归的开销。
前面提过，有多种选择基准值的方法。可以尝试使用三数取中法避免切分不均匀，即在选择基准值时考虑列表的头元素、中间元素与尾元素。本例中，先选取元素 54、77 和 20，然后取中间值 54 作为基准值（当然，它也是之前选择的基准值）。这种方法的思路是，如果头元素的正确位置不在列表中部附近，那么三元素的中间值将更靠近中部。当原始列表的起始部分已经有序时，这一招尤其管用。我们将这种基准值选法的实现留作练习。