1. 简介

排序与我们日常生活中息息相关，比如，我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程序设计中，排序和查找也是最基本的算法，很多其他的算法都是以排序算法为基础，在一般的数据处理或分析中，通常第一步就是进行排序，比如说二分查找，首先要对数据进行排序

排序的算法有很多，在维基百科上有这么一个分类，另外大家有兴趣也可以直接上维基百科上看相关算法

2. 选择排序

原理

选择排序很简单，他的步骤如下：

1. 从左至右遍历，找到最小(大)的元素，然后与第一个元素交换。

2. 从剩余未排序元素中继续寻找最小（大）元素，然后与第二个元素进行交换。

3. 以此类推，直到所有元素均排序完毕。

之所以称之为选择排序，是因为每一次遍历未排序的序列我们总是从中选择出最小的元素。

实现

```

def selection_sort(list2):

      for i in range(0, len (list2)):

           min = i

           for j in range(i + 1, len(list2)):

                if list2[j] < list2[min]:

                    min = j

                     list2[i], list2[min] = list2[min], list2[i]  # swap

```

*选择排序需要花费 (N – 1) + (N – 2) + … + 1 + 0 = N(N- 1) / 2 ~ N2/2次比较 和 N-1次交换操作。

*对初始数据不敏感，不管初始的数据有没有排好序，都需要经历N2/2次比较，这对于一些原本排好序，或者近似排好序的序列来说并不具有优势。在最好的情况下，即所有的排好序，需要0次交换，最差的情况，倒序，需要N-1次交换。

*数据交换的次数较少，如果某个元素位于正确的最终位置上，则它不会被移动。在最差情况下也只需要进行N-1次数据交换，在所有的完全依靠交换去移动元素的排序方法中，选择排序属于比较好的一种。

3. 插入排序
原理

插入排序也是一种比较直观的排序方式。可以以我们平常打扑克牌为例来说明，假设我们那在手上的牌都是排好序的，那么插入排序可以理解为我们每一次将摸到的牌，和手中的牌从左到右依次进行对比，如果找到合适的位置则直接插入。具体的步骤为：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素小于前面的元素（已排序），则依次与前面元素进行比较如果小于则交换，直到找到大于该元素的就则停止；

4. 如果该元素大于前面的元素（已排序），则重复步骤2

5. 重复步骤2~4 直到所有元素都排好序

实现

3. 希尔排序

原理：

希尔排序也称之为递减增量排序，他是对插入排序的改进。在第二部插入排序中，我们知道，插入排序对于近似已排好序的序列来说，效率很高，可以达到线性排序的效率。但是插入排序效率也是比较低的，他一次只能将数据向前移一位。比如如果一个长度为N的序列，最小的元素如果恰巧在末尾，那么使用插入排序仍需一步一步的向前移动和比较，要N-1次比较和交换。

希尔排序通过将待比较的元素划分为几个区域来提升插入排序的效率。这样可以让元素可以一次性的朝最终位置迈进一大步，然后算法再取越来越小的步长进行排序，最后一步就是步长为1的普通的插入排序的，但是这个时候，整个序列已经是近似排好序的，所以效率高。

实现：

可以看到，希尔排序的实现是在插入排序的基础上改进的，插入排序的步长为1，每一次递减1，希尔排序的步长为我们定义的h，然后每一次和前面的-h位置上的元素进行比较。算法中，我们首先获取小于N/3 的最大的步长，然后逐步长递减至步长为1的一般的插入排序。

分析：

1. 希尔排序的关键在于步长递减序列的确定，任何递减至1步长的序列都可以，目前已知的比较好的序列有：

Shell’s 序列: N/2 , N/4 , …, 1 (重复除以2);

Hibbard’s 序列: 1, 3, 7, …, 2k – 1 ;

Knuth’s 序列: 1, 4, 13, …, (3k – 1) / 2 ;该序列是本文代码中使用的序列。

已知最好的序列是 Sedgewick’s (Knuth的学生，Algorithems的作者)的序列: 1, 5, 19, 41, 109, ….

该序列由下面两个表达式交互获得:

1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…

5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …

“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

2. 希尔排序的分析比较复杂，使用Hibbard’s 递减步长序列的时间复杂度为O(N3/2)，平均时间复杂度大约为O(N5/4) ,具体的复杂度目前仍存在争议。

3. 实验表明，对于中型的序列( 万)，希尔排序的时间复杂度接近最快的排序算法的时间复杂度nlogn。

4. 快速排序

原理：

快速排序的基本思想如下：

1. 对数组进行随机化。

2. 从数列中取出一个数作为中轴数(pivot)。

3. 将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。

4. 再对左右区间重复第三步，直到各区间只有一个数。

操作可以分为以下5个步骤：

获取中轴元素

1. i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]

2. j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]

3. 交换a[i]和a[j]

4. 重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。

实现