# 07 基于比较的排序(上)

![linkedlist](/images/algo/sort/sort_image.jpg)
基于比较的排序算法: 冒泡排序、插入排序和选择排序

<!-- more -->

## 1. 排序算法要点
排序算法太多了，因此除了要学习各种算法的原理，代码实现之外；我们还要搞明白如何比较和分析一个排序算法。评价一个算法可以从如下几个方面入手:
1. 算法的执行效率:
  - 算法的执行效率包括最好情况、最坏情况、平均情况的时间复杂度；之所以要区分这三种情况，是因为大多数排序算法在不同有序度的数据集上的时间复杂度不相同
  - 时间复杂度的系数、常数 、低阶；通常我们要排序的数剧集并不大，因此需要将系数、常数 、低阶考虑进来
  - 比较次数和交换（或移动）次数，基于比较的排序算法需要进行数据的比较和移动两个操作，因此需要把这两个操作考虑进来
2. 排序算法的内存消耗，排序算法中，我们将空间复杂度为O(1) 的算法称为原地排序算法
3. 排序算法的稳定性，稳定性指如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

这些方面可以帮助我们分析和更好的理解每种算法的特点。

## 1.1 排序算法分类
排序算法太多了，最经典的、最常用的包括：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。如上图所示按照时间复杂度它们分成了三类。

![linkedlist](/images/algo/sort/sort_image.jpg)

本节我们先来介绍基于比较的排序算法:冒泡排序、插入排序和选择排序。

![linkedlist](/images/algo/sort/compare.jpg)

这三种时间复杂度为 O(n2) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。后面讲排序优化的时候，我会讲到，有些编程语言中的排序函数的实现原理会用到插入排序算法。

## 1.2 有序度
有序度是数组中具有有序关系的元素对的个数，逆序度恰恰相反，完全有序的数组的有序度叫作满有序度。逆序度的定义正好跟有序度相反显然 `逆序度 = 满有序度 - 有序度`。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，排序完成。

在下面的冒泡和插入排序的实现中，我们会发现无论是插入排序还是选择排序，每次数据交换只会增加 1 个有序度(因为它们只会对相邻的元素进行交换)。因此这两种排序的数据交换次数是相同的都是数剧集的逆序度。但是冒泡排序的实现更复杂需要更多次的赋值操作。所以如果将时间复杂度的系数、常数 、低阶考虑进来，冒泡排序并没有插入排序快。

## 2. 实现
### 2.1 冒泡排序
冒泡排序的核心是**每次只会操作相临的两个数据**，比较它们的大小，并在不满足大小关系时交换；在 n 次操作之后将最大或者最小值移动到最前端。

总共经过 n 次冒泡之后，排序即可完成。冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

冒泡是原地排序算法，只要我们在代码中不交换相等的元素，冒泡排序就是稳定的排序算法

![linkedlist](/images/algo/sort/Bubble.jpg)

```python
def sort_bubble(alist):
    for end in range(len(alist), 1, -1):
        for i in range(1, end):
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
```

### 2.2 插入排序
插入排序将数据分为**已排序**和**未排序**两个区间，然后不断取未排序区间中的元素插入到已排序区间中，并保持已排序区间的有序；重复直至未排序区间为空即可。

插入排序是原地排序算法，在插入排序中，对于值相等的元素，我们只要将后出现的元素插入到后出现元素的后面，插入排序就是稳定的排序算法。

![linkedlist](/images/algo/sort/insert.jpg)

```python
def sort_insert(alist):
    for end in range(1, len(alist)):
        tmp = alist[end]
        p = end - 1
        while p >= 0 and alist[p] > tmp:
            alist[p + 1] = alist[p]
            p -= 1
        alist[p + 1] = tmp
```

### 2.3 选择排序
选择排序将数据分为**已排序**和**未排序**两个区间，不同的是选择排序每次会从未排序区间找出最小的元素放到已排序区间的末尾，而不是插入。

选择排序是原地排序算法，最好最坏和平均时间复杂度都是O(n2)，但是选择排序并不是稳定的排序算法。原因是选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样就破坏了稳定性。

![linkedlist](/images/algo/sort/select.jpg)

```python
def sort_select(alist):
    for start in range(0, len(alist)):
        m = start
        for i in range(start + 1, len(alist)):
            if alist[i] < alist[m]:
                m = i
        alist[start], alist[m] = alist[m], alist[start]
```

**参考:**
- [王争老师专栏-数据结构与算法之美](https://time.geekbang.org/column/126)
- [《数据结构与算法：python语言实现》](https://book.douban.com/subject/30323938/)