数据结构与算法第七讲 - 排序（上）

对于排序算法，主要掌握内容如下：

• 排序算法的实现原理
• 手写出实现代码
• 评价及分析算法

本讲内容

如何分析一个排序算法
冒泡排序
插入排序
选择排序

思考题：插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？

如何分析一个排序算法？

排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度
   有序度不同的数据，算法的时间复杂度不同
2. 时间复杂度的系数、常数 、低阶
   时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。
   但在实际开发中，排序算法中的数据集一般是有限的，有的可能还比较小，所以这个时候不能忽略系数、常数、低阶，要考虑进去
3. 比较次数和交换（或移动）次数
   基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。
   TODO：那些是基于比较的排序算法

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。
针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。
原地排序算法，就是特指空间复杂度是 O(1) 的排序算法

排序算法的稳定性

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
为什么要引入稳定性？
对于纯数据的排序，数据是否改变顺序没什么影响
但实际业务开发过程中，大多是对一个对象进行排序，而一个对象有多个属性。

比如我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？

最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：

1. 先按照下单时间给订单排序，注意是按照下单时间，不是金额。
2. 排序完成之后，用稳定排序算法，按照订单金额重新排序。
   两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。因为稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

冒泡排序（Bubble Sort）

原理：

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

代码实现：

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

算法分析：

• 原地排序算法，即空间复杂度为O（1），因为只有在进行数据交换时申请一个临时空间用于交换数据
• 稳定排序算法，相同的元素排序前后顺序没有改变

• 时间负复杂度：最好O（n），最坏O(n2），平均O（n2）
  TODO：平均复杂度的计算过程
  借助于有序度，逆序度和满有序度进行计算
  有序度：数组中具有有序关系的元素对的个数。有序元素对：a[i] <= a[j], 如果i < j。

  
  有序度

对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n(n-1)/2，也就是 15。
我们把这种完全有序的数组的有序度叫作满有序度*。

逆序度：

插入排序

原理：

一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？

• 遍历数组，找到数据应该插入的位置将其插入即可。
  插入数据前，要把要插入位置之后的数据进行后移，腾挪出空间给新插入的数据

  
  有序数组插入一个新元素

上面一个动态排序的过程，即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。

而对于一个静态的数组，我们如何借鉴上面的插入思想保证其有序呢？

• 将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
  插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

思考：对于一个给定的数据序列，使用插入排序算法使其有序，需要移动多少次元素？
解答：移动次数是固定的，等于逆序度

代码实现：

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

算法分析：

• 原地排序算法
• 稳定排序算法
• 时间复杂度：最好O（n），最坏O(n2），平均O（n2）

选择排序

原理：

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码：

算法分析

• 原地排序算法
• 非稳定排序算法
• 最好，最坏和平均时间复杂度都是O（n2）

排序画图工具：https://visualgo.net/en