排序算法

大部分编程语言，都会提供排序函数，平常项目，也会经常使用排序

最经典，最常用的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序

排序算法时间复杂度是否基于比较
冒泡、插入、选择O(n²)是
快排、归并O(nlogn)是
桶、计数、基数O(n)否

---

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

---

1. 如何分析一个“排序算法”？

学习排序算法，我们除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法，要从哪几个方面入手呢？

排序算法的执行效率

一般会从这几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度

要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

为什么要区分这三种时间复杂度呢？

第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。

第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

2. 时间复杂度的系数、常数 、低阶

时间复杂度反应的是数据规模n很大的时候的一个增长趋势，实际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量

针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。我们今天讲的三种排序算法，都是原地排序算法。

排序算法的稳定性

针对排序算法，我们还有一个重要的度量指标，稳定性。如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

• 为什么要考察排序算法的稳定性呢？
  
  

真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。

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

最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

2 冒泡排序1. 概念

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

2. 代码实现public class BubbleSort {
  // 冒泡排序，a表示数组，n表示数组大小
  public static 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 temp = a[j];
          a[j] = a[j+1];
          a[j+1] = temp;
          // 标志位
          flag = true;
        }
      }
      if(!flag) break;//没有数据交换，提前退出
    }
  }
​
  public static void main(String[] args) {
    int[] a = {1,2,7,5,9,3};
    bubbleSort(a,a.length);
    for (int i = 0; i < a.length; i++) {
      System.out.println(a);
    }
  }
}3. 问题描述1. 冒泡排序是原地排序算法吗？

只涉及相邻数据的交换操作，只需要长良机的临时空间，空间复杂度为O(1)，原地排序

2. 冒泡排序是稳定的排序算法吗？

只有交换才改变两个元素的前后顺序，为保证冒泡算法稳定性，相邻两个元素大小相等时，不做交换，相同大小的数据在排序前后顺序不变，稳定

3. 冒泡排序的时间复杂度

最好情况，有序，只需要进行一次冒泡，就可以结束，时间复杂度为O(n)；最坏，倒序排列，n次冒泡，最坏时间复杂度为O(n²)

平均时间复杂度，对于包含n个数据的数组，n个数据有n!种排列方式。不同排列方式，执行时间不同。有一种思路，通过“有序度”和“逆序度”两个概念分析

有序度是数组中具有有序关系的元素对的个数。数学表达式：有序元素对：a<=a[j]，如果i<j

对于倒序排列的数组，有序度为0；完全有序的，有序度n*(n-1)/2，完全有序的有序度叫²

逆序度相反，默认从小到大为有序。逆序元素对：a>a[j]，如果i<j

逆序度=满有序度-有序度，排序过程就是增加有序度，减少逆序度，最后达到满有序度

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度加1，交换次数确定，也就是逆序度，为n*(n-1)/2-初始有序度

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况，初始有序度0，进行n*(n-1)/2 次交换。最好情况，初始有序度为n*(n-1)/2 ，不需要交换，取中间值n*(n-1)/4 ，表示初始有序度的平均情况

也就是说，平均情况，需要n*(n-1)/4 次交换，比较操作肯定比交换操作多，而复杂度的上限为O(n²)，因此平均时间复杂度就是O(n²)

3. 插入排序（Insertion Sort）

一个有序的数组，往里面添加一个新的数据，如何继续保持数据有序呢？只要遍历数组，找到数据应该插入的位置将其插入。

这是个动态过程，动态的往有序集合添加数据，通过该方法保持集合中的数据一直有序。而对于静态数据，也可以借鉴上面的过程。

插入排序具体是如何借助上面的思想实现排序呢？

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

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

对于不同的查找插入点方法（从头到尾，从尾到头），元素比较次数有区别。但对于一个给定的初始序列，移动操作的次数固定，等于逆序度。

看马士兵老师的视频，非常形象，比喻为打扑克，斗地主，接牌后怎么给手里的牌排序？就是插入排序！

代码实现public class InsertionSort {
  // 插入排序，a表示数组，n表示数组大小
  public static void insertionSort(int[] a, int n) {
    if (n <= 1) return;
​
    for (int i = 1; i < n; i++) {
      int value = a;
      // 指针，从i-1开始，每次都和后边的值比大小，挪位置，直到确定位置
      int j = i - 1;
      // 查找插入的位置
      for (; j >= 0; j--) {
        if (a[j] > value) {
          a[j + 1] = a[j]; //数据移动
        } else {
          break;
        }
      }
      a[j + 1] = value; // 插入数据
    }
  }
​
  public static void main(String[] args) {
    int[] a = {1,3,7,9,2,4};
    insertionSort(a,a.length);
    for (int i = 0; i < a.length; i++) {
      System.out.println(a);
    }
  }
}3. 三个问题描述1. 插入排序是原地排序吗

插入排序的运行不需要额外的存储空间，空间复杂度为O(1)，原地排序

2. 插入排序稳定吗

在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后边，保持原有的前后顺序不变，稳定。

3. 插入排序的时间复杂度

如果已经有序，从尾到头查找插入位置，每次只需要比较一个数据就能确定插入的位置，最好时间复杂度为O(n)，注意：这是从尾到头遍历已经有序的数据。

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

我们在数组中插入一个数据的平均时间复杂度为O(n)，对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，平均时间复杂度为O(n²)

4. 选择排序（Selection Sort）

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

快排的时间复杂度为O(1)，是一种原地排序算法。选择排序的最好时间复杂度、最坏和平均时间复杂度都是O(n²)

选择排序不稳定，每次都要找剩余未排序元素的最小值，并和前面的元素交换位置，破坏了稳定性。

比如5,8,5,2,9，使用选择排序，第一次找到最小元素2，与第一个5交换位置，第一个5和中间的5的顺序就变了，不稳定。

5. 解答开篇

冒泡排序和插入排序的时间复杂度都是O(n²)

排序算法

大部分编程语言，都会提供排序函数，平常项目，也会经常使用排序

最经典，最常用的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序

排序算法时间复杂度是否基于比较
冒泡、插入、选择O(n²)是
快排、归并O(nlogn)是
桶、计数、基数O(n)否

---

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

---

1. 如何分析一个“排序算法”？

学习排序算法，我们除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法，要从哪几个方面入手呢？

排序算法的执行效率

一般会从这几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度

要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

为什么要区分这三种时间复杂度呢？

第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。

第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

2. 时间复杂度的系数、常数 、低阶

时间复杂度反应的是数据规模n很大的时候的一个增长趋势，实际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量

针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。我们今天讲的三种排序算法，都是原地排序算法。

排序算法的稳定性

针对排序算法，我们还有一个重要的度量指标，稳定性。如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

• 为什么要考察排序算法的稳定性呢？
  
  

真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。

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

最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

2 冒泡排序1. 概念

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

2. 代码实现public class BubbleSort {
  // 冒泡排序，a表示数组，n表示数组大小
  public static 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 temp = a[j];
          a[j] = a[j+1];
          a[j+1] = temp;
          // 标志位
          flag = true;
        }
      }
      if(!flag) break;//没有数据交换，提前退出
    }
  }
​
  public static void main(String[] args) {
    int[] a = {1,2,7,5,9,3};
    bubbleSort(a,a.length);
    for (int i = 0; i < a.length; i++) {
      System.out.println(a);
    }
  }
}3. 问题描述1. 冒泡排序是原地排序算法吗？

只涉及相邻数据的交换操作，只需要长良机的临时空间，空间复杂度为O(1)，原地排序

2. 冒泡排序是稳定的排序算法吗？

只有交换才改变两个元素的前后顺序，为保证冒泡算法稳定性，相邻两个元素大小相等时，不做交换，相同大小的数据在排序前后顺序不变，稳定

3. 冒泡排序的时间复杂度

最好情况，有序，只需要进行一次冒泡，就可以结束，时间复杂度为O(n)；最坏，倒序排列，n次冒泡，最坏时间复杂度为O(n²)

平均时间复杂度，对于包含n个数据的数组，n个数据有n!种排列方式。不同排列方式，执行时间不同。有一种思路，通过“有序度”和“逆序度”两个概念分析

有序度是数组中具有有序关系的元素对的个数。数学表达式：有序元素对：a<=a[j]，如果i<j

对于倒序排列的数组，有序度为0；完全有序的，有序度n*(n-1)/2，完全有序的有序度叫²

逆序度相反，默认从小到大为有序。逆序元素对：a>a[j]，如果i<j

逆序度=满有序度-有序度，排序过程就是增加有序度，减少逆序度，最后达到满有序度

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度加1，交换次数确定，也就是逆序度，为n*(n-1)/2-初始有序度

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况，初始有序度0，进行n*(n-1)/2 次交换。最好情况，初始有序度为n*(n-1)/2 ，不需要交换，取中间值n*(n-1)/4 ，表示初始有序度的平均情况

也就是说，平均情况，需要n*(n-1)/4 次交换，比较操作肯定比交换操作多，而复杂度的上限为O(n²)，因此平均时间复杂度就是O(n²)

3. 插入排序（Insertion Sort）

一个有序的数组，往里面添加一个新的数据，如何继续保持数据有序呢？只要遍历数组，找到数据应该插入的位置将其插入。

这是个动态过程，动态的往有序集合添加数据，通过该方法保持集合中的数据一直有序。而对于静态数据，也可以借鉴上面的过程。

插入排序具体是如何借助上面的思想实现排序呢？

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

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

对于不同的查找插入点方法（从头到尾，从尾到头），元素比较次数有区别。但对于一个给定的初始序列，移动操作的次数固定，等于逆序度。

看马士兵老师的视频，非常形象，比喻为打扑克，斗地主，接牌后怎么给手里的牌排序？就是插入排序！

代码实现public class InsertionSort {
  // 插入排序，a表示数组，n表示数组大小
  public static void insertionSort(int[] a, int n) {
    if (n <= 1) return;
​
    for (int i = 1; i < n; i++) {
      int value = a;
      // 指针，从i-1开始，每次都和后边的值比大小，挪位置，直到确定位置
      int j = i - 1;
      // 查找插入的位置
      for (; j >= 0; j--) {
        if (a[j] > value) {
          a[j + 1] = a[j]; //数据移动
        } else {
          break;
        }
      }
      a[j + 1] = value; // 插入数据
    }
  }
​
  public static void main(String[] args) {
    int[] a = {1,3,7,9,2,4};
    insertionSort(a,a.length);
    for (int i = 0; i < a.length; i++) {
      System.out.println(a);
    }
  }
}3. 三个问题描述1. 插入排序是原地排序吗

插入排序的运行不需要额外的存储空间，空间复杂度为O(1)，原地排序

2. 插入排序稳定吗

在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后边，保持原有的前后顺序不变，稳定。

3. 插入排序的时间复杂度

如果已经有序，从尾到头查找插入位置，每次只需要比较一个数据就能确定插入的位置，最好时间复杂度为O(n)，注意：这是从尾到头遍历已经有序的数据。

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

我们在数组中插入一个数据的平均时间复杂度为O(n)，对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，平均时间复杂度为O(n²)

4. 选择排序（Selection Sort）

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

快排的时间复杂度为O(1)，是一种原地排序算法。选择排序的最好时间复杂度、最坏和平均时间复杂度都是O(n²)

选择排序不稳定，每次都要找剩余未排序元素的最小值，并和前面的元素交换位置，破坏了稳定性。

比如5,8,5,2,9，使用选择排序，第一次找到最小元素2，与第一个5交换位置，第一个5和中间的5的顺序就变了，不稳定。

5. 解答开篇

冒泡排序和插入排序的时间复杂度都是O(n²)