数据结构与算法之美-排序(一)

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

1. 排序算法

1.1 介绍

下面是我们常用的 8 种排序算法，按照时间复杂度分成了三类，如下图

image.png

1.2 排序算法的执行效率

• 最好情况、最坏情况、平均情况时间复杂度
  以及对应的要排序的原始数据，有序度不同的数据，对于排序的执行时间是有影响的

• 时间复杂度的系数、常数、低阶
  时间复杂度反映的是数据规模 n 很大时的一个增长趋势，会忽略系数、常数、低阶，但实际开发中，排序的可能是 10 个、100 个、1000 个数据，在对同一阶时间复杂度的排序算法性能对比时，需要把系数、常数、低阶考虑进来。

• 比较次数和交换（移动）次数
  基于比较的排序算法的执行过程，会涉及两种操作：比较大小和元素交换或移动，也需要考虑进去

1.3 排序算法的内存消耗

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

1.4 排序算法的稳定性

什么是稳定的排序算法？就是如果待排序序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变，否则就是不稳定的排序算法。

举个例子，比如有一组数据 2 9 3 4 8 3，按照大小排序之后就是 2 3 3 4 8 9，经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那这种排序算就是稳定的排序算法，否则就是不稳定的排序算法。

2. 有序度&逆序度

• 有序度是数组中具有有序关系的元素对的个数

  
  image.png

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

逆序度的定义和有序度相反，并且逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，说明排序完成。

3. 冒泡排序

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

对一组数据 4，5，6，3，2，1，从小到大进行排序，第一次冒泡操作示例如下：

image.png

经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上了，要想完成所有数据的排序，我们只要进行 6 次冒泡操作就行了：

image.png

我们可以对相面的冒泡过程进行优化，当某次冒泡操作没有数据交换时，说明已经达到完全有序，不需要在进行后续的冒泡操作，如下图：

image.png

代码如下：

// 冒泡排序，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^2)

  
  image.png

4. 插入排序

主要思想就是在有序的数组中，通过遍历数组，将新的数据插入到合适的位置，继续保持数组有序：

image.png

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

image.png

代码如下：

// 插入排序，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(1)，为原地排序算法
• 是稳定的排序算法，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面元素的后面，保持原有的前后顺序不变
• 平均时间复杂度为 O(n^2)

5. 选择排序

选择排序实现思路类似于插入排序，也分为已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾（交换）：

image.png

• 选择排序空间复杂度为 O(1)，也是一种原地排序算法
• 时间复杂度为 O(n^2)
• 选择排序是一种不稳定的排序算法，相对于冒泡排序和插入排序，选择排序稍微逊色

6. 总结

冒泡排序不管怎么优化，元素交换的次数总是原始数据的逆序度；
插入排序不管怎么优化，元素移动的次数也是原始数据的逆序度。

从代码实现上看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡排序需要 3 个赋值操作，插入排序只需要 1 个，所以插入排序要优于冒泡排序：

冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

• 分析&评价一个排序算法，要从执行效率、内存消耗和稳定性三个方面来看

image.png