[TOC]

本节主要介绍排序算法。

首先思考一个问题：为什么插入排序比冒泡排序更受欢迎？

排序

排序的定义：一些列对象按照逻辑排序。例如账单按照消费日期倒序排列。

冒泡排序 Bubble Sort

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

优化：可以提前结束冒泡排序

public static void bubbleSort(int[] a) {
      if(a==null || a.length == 0){
        throw new IllegalArgumentException("array is null or no element!");
      }
      int n = a.length;
      for (int i = 0; i < n; i++) {
        boolean flag = false; // 提前退出冒泡循环的标志位
        for (int j = 0; j < n - 1 - i; j++) {
          if (a[j] > a[j + 1]) {
            exch(a, j, j + 1);
            flag = true; // 表示有数据交换
          }
        }
        if (!flag){
          StdOut.println("提前退出");
          break; // 没有数据交换，提前退出。
        }
      }
    }
  }

有三个问题：

**第一、冒泡排序是原地排序算法么？**

冒泡的排序过程只涉及相邻数据的交换操作，只需要常量级别的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

**第二、冒泡排序算法是稳定排序算法么？**

在冒泡排序中，只有一个元素大于相邻的元素时才做交换，相等的相邻元素不做交换。相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

**第三、冒泡排序的时间复杂度是多少？**

最好情况：123456 1次冒泡 时间复杂度O(n)

最坏情况：654321 5次冒泡 时间复杂度O(n^2)

平均时间复杂度就是加权平均期望时间复杂度，简单的说是O(n^2)

这里涉及到几个概念：有序度，满有序度，逆序度 = 满有序度 - 有序度。

平均情况下要进行 n*(n-1)/4 次交换操作。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。 对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。 换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。 这个平均时间复杂度推导过程其实并不严格，但是很多时候很实用，毕竟概率论的定量分析太复杂，不太好用。等我们讲到快排的时候，我还会再次用这种“不严格”的方法来分析平均时间复杂度。

插入排序 Insertion Sort

记得小时候玩扑克排么？我们通常抓新的牌放到手里，牌的位置是插入到已有的牌中，手中的牌是有序的。这就是插入排序的思想了。

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

**代码如下：**

public static void InsertionSort(int[] a) {
      if (a == null || a.length == 0) {
        throw new IllegalArgumentException("array is null or no element!");
      }
      int n = a.length;
      for (int i = 1; i < n; i++) { // 无序数组部分
        int temp = a[i];
        int j;
        for (j = i - 1; j >= 0; j--) { // 有序数组部分
          if (temp < a[j]) {
            a[j + 1] = a[j];
          } else {
            break;
          }
        }
        a[j + 1] = temp; // 因为j--，位置差一
      }
    }

现在，我们来看点稍微复杂的东西。这里有三个问题：

**第一、插入排序是原地排序算法吗？**

从实现过程可以看出，插入排序算法的运行不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。

**第二、插入排序是稳定的排序算法吗？**

在插入排序中，对于值相同的元素，我们可以选择项后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

**插入排序的时间复杂度是多少？**

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好的时间复杂度为O(n)。注意，这里 **从尾到头遍历已经有序的数据。**

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n^2)。

还记得我们再数组中插入一个数据的平均时间复杂度是多少吗？没错，是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n^2)。

选择排序 Selection Sort

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

选择排序空间复杂度为O(1)，是一种原地排序算法。

选择排序的最好情况时间复杂度，最坏情况和平均情况时间复杂度都为O(n^2)。

若数组已经有序，每次循环都要找到最小值，复杂度为O(n^2)。区别在于是否交换。

**选择排序是稳定排序算法吗？** 答案是否定的，选择排序是一种不稳定排序的算法。

比如5,8,5,2,9 这样一组数据，使用选择排序算法来排序的话。第一次找到最小元素为2，与第一个5交换位置，第一个5与中间的5的顺序就变了，所以就不稳定了。 **正是如此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。**

解答开篇

基本的知识都讲完了，我们来看开篇的问题：冒泡排序和插入排序的时间复杂度都是O(n^2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？

我们分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值。 是原始数据的逆序度。 插入排序也是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。

但是，从代码实现上来看，冒泡排序的交换要比插入排序的数据移动要复杂。冒泡排序需要3个赋值操作，而插入排序只需要1个。我们来看这段操作：

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

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

我们把执行一个赋值语句的时间粗略的计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。用冒泡排序需要K次交换操作，每次需要3个赋值语句，所以总交换耗时就是3*K单位时间。而插入排序中的数据移动操作只需要K个单位时间。

这个只是非常理论的分析。下面实验一下。使用10000个数组，每个数组中包含200个数据。分别运行冒泡和插入排序。

@Test
  public void testSortCompare(){
    int[] a;
    Stopwatch time = new Stopwatch();
    int N = 10000;
    for (int i = 0; i < N; i++) {
      a = ArrayGenerator.randomIntsArray(200);
      Sort.InsertionSort(a);
//      PrintUtil.show(a);
    }
    StdOut.println(time.elapsedTime());

    time = new Stopwatch();
    for (int i = 0; i < N; i++) {
      a = ArrayGenerator.randomIntsArray(200);
      Sort.bubbleSort(a);
//      PrintUtil.show(a);
    }
    StdOut.println(time.elapsedTime());
  }

运行时间分别是：(单位是秒)

0.279
0.972

内容小节

要想分析、平均一个排序算法，需要从执行效率、内存消耗和稳定性三个方面来看。因此，这一节，我带你分析了三种时间复杂度是O(n^2)的排序算法，冒泡排序、插入排序、选择排序。你需要重点掌握的是它们的分析方法。

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

对于大规模数据以上三种算法的时间复杂度有点高，下一节讲时间复杂度为O(nlogn)的排序算法。

附录

**排序算法动画：**

https://www.toptal.com/developers/sorting-algorithms