交换类排序法

排序

所谓排序是指将一个无序序列整理成按值非递减的有序序列。根据排序序列的规模以及对数据处理的要求，可以采用不同的排序方法；

交换类排序法

交换类排序法是借助数据元素的“交换”来进行排序的一种方法。本小节介绍两种，冒泡排序法和快速排序法；

冒泡排序法

冒泡排序（Bubble Sort）的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。（一次排序排好一个元素）

冒泡排序每一遍的从前往后扫描都把排序范围内最大元素沉到了表的底部，每一遍的从后往前扫描，都把排序范围内的最小元素像气泡一样浮到了表的最前面。冒泡排序的名称也由此而来。

快速排序法

在冒泡排序种，一次扫描只能确保最大的元素或最小的元素移动到了正确的位置，而未排序序列的长度可能只减少了1.快速排序（Quick Sort）是对冒泡排序方法的一种本质改进。

快速排序的基本思想是：在待排序的n个元素中取一个元素K（通常取第一个元素），以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样以K为分界线，把线性表分割成了两个子表，这称为一趟排序。然后对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表长度为1为止，这时，线性表已经是排好序的了。

Python实现：对给定数组用快速排序法进行排序

def quicksort(array):
  if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
    #基准条件：为空或者只包含一个元素的数组是有序的，直接返回即可；
    return array
  else:
    # recursive case#递归条件，默认将第一个元素作为基准值；
    pivot = array[0]
    # sub-array of all the elements less than the pivot
    #由所有小于基准值的元素组成的子数组
    less = [i for i in array[1:] if i <= pivot]
    # sub-array of all the elements greater than the pivot
    #由所有大于基准值的元素组成的子数组
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)
    #分别对，左右两个子数组采取同样地处理；

print (quicksort([10, 5, 2, 3]))
#我去，递归NB
输出：
[2, 3, 5, 10]

分而治之

本章的重点是使用学到的新技能来解决问题。我们将探索分而治之 （divide and conquer，D&C）——一种著名的递归式问题解决方法。 面对新问题时，你不再束手无策，而是自问：“使用分而治 之能解决吗？” 你将学习第一个重要的D&C算法——快速排序。

这里重申一下D&C的工作原理：

(1) 找出简单的基线条件；

(2) 确定如何缩小问题的规模，使其符合基线条件。

D&C并非可用于解决问题的算法，而是一种解决问题的思路。

例子一

书中举了如何均匀将一块地分割成多块正方形，并让这些正方形最大的例子。这个例子里的基准条件是最简单的情形，一块地的长和宽是整数倍关系，这样直接平分就好了。

那如何缩小规模呢？不断地划分出最大的方块，然后对余下的土地进行同样地操作，不断地让自己需要面对的地越来越小，以至于最后这剩余的土地达到基准条件。能够满足一小片地的正方形也能满足一大片地，这需要去理解欧几里得算法。

例子二

第二个例子是给定一个数组，如何将里面的数字加起来。

第一步，确定基准条件。什么情况下最简单？数组为空或者数组只包含一个元素时，统计总和最简单。

第二步，缩小规模。通过不断递归调用，使得情况向基准条件靠近。也就是不断拆分数组，让其最后只有包含一个元素，反正这过程中递归会记录状态，到时候再将这些拆掉的全加起来就行了。

例子三，使用快速排序对数组进行排序

第一步，设定基准条件。最简单的情形就是数组为空或者只有一个元素，根本不需要进行排序；对于两个元素的也很好排序，交换位置就行了。

第二步，缩小问题规模，使得情况向基准条件靠近。

快速排序的工作原理：

第一步，设定基准值。

第二步，然后让它两边分别是比它小或比它大的数字。

第三步，分别对两边的子数组进行排序；

由于归纳推理原理，对两个元素数组适用的也适用于有三元素的数组，进而也适用于有四元素数组……有N元素数组。

归纳证明

刚才你大致见识了归纳证明！归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。是不是有点似曾相识的感觉？

例如，假设我要证明我能爬到梯子的最上面。 递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果我站 在第二个横档上，就能爬到第三个横档。这就是归纳条件。

而基线条件是这样的，即我已经站 在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。

对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个 元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两 个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用， 以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明， 但它很有趣，并与D&C协同发挥作用。

小结

1. D&C将问题逐步分解。

2. 使用D&C处理列表时，基线条件很可能是空数组或只包含一个元 素的数组。

3. 实现快速排序时，请随机地选择用作基准值的元素。

4. 快速排序的平均运行时间为O(n log n)。

5. 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。

6. 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。