分类

冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

image.png

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

排序算法的效率

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

之所以要区分这三种时间复杂度。第一是因为有些排序算法会区分，为了好对比，我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

考虑时间复杂度的系数、常数 、低阶

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

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

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。
冒泡、插入、选择都是原地排序

排序算法的稳定性

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。

经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

为何需要考察算法的稳定性？
算法稳定性的用处，多次排序中，下一次排序需要依赖上一次排序的稳定结果。比如订单排序中，先按时间排序，再使用稳定排序算法按价格排序，最终要得到同个价格的订单按下单时间排序，就需要算法稳定性。

有序度、逆序度

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

  1. 有序元素对：a[i] <= a[j], 如果i < j。

image.png

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

逆序度
**

  1. 逆序元素对：a[i] > a[j], 如果i < j。

冒泡排序

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

  1.     public static int [] bubbleSort(int[] nums){
  2.         int n=nums.length;
  3.         int temp;
  4.         for (int i = 0; i<n-1; i++) {
  5.             for (int j=0;j<n-i-1;j++){
  6.                 if (nums[j]>nums[j+1]){
  7.                     temp=nums[j];
  8.                     nums[j]=nums[j+1];
  9.                     nums[j+1]=temp;
  10.                 }
  11.             }
  13.         }
  14.         return nums;
  16.     }

进行冒泡排序时，数组长度为n，最坏的情况需要n次冒泡，但因为数据量以及数据的有序性不同，可能不需要n次数组就已经排好序了 ，后续的冒泡就是对性能的消耗。我们可以根据本轮冒泡是否交换元素，来判断数组是否已经排好序了。

  1. public static int [] bubbleSort(int[] nums){
  3.         //冒泡排序：冒泡排序只会操作相邻的两个数据。
  4.         // 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
  5.         // 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
  6.         int n=nums.length;
  7.         int temp;
  8.         for (int i = 0; i<n-1; i++) {
  9.             //提前退出冒泡循环的标志位
  10.             boolean flag = false;
  12.             for (int j=0;j<n-i-1;j++){
  13.                 if (nums[j]>nums[j+1]){
  14.                     temp=nums[j];
  15.                     nums[j]=nums[j+1];
  16.                     nums[j+1]=temp;
  17.                     flag=true;  //有数据交换
  18.                 }
  19.             }
  20.             if(!flag) break; // 本轮没有发生数据交换，数组已排好序
  22.         }
  23.         return nums;
  25.     }

冒泡排序的分析
**
第一，冒泡排序是原地排序算法吗？

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

第二，冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

第三，冒泡排序的时间复杂度是多少？
image.png
平均时间复杂度就是加权平均期望时间复杂度。

换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。

插入排序

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

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。

  1.     public static void insertionSort(int[] nums){
  2.         //插入排序：数组分为两个区间，一个已排序区间和未排序区间。
  3.         // 取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，
  4.         // 并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
  6.         int n = nums.length;
  7.         if (n<=1) return ;
  9.         for (int i = 1; i <n ; i++) {
  10.             //取出待插入元素
  11.             int value =nums[i];
  12.             //已排好序的区间
  13.             int j =i-1;
  14.             //遍历得到待插入的位置
  15.             for (;j>=0;j--){
  16.                 if (nums[j]>value){
  17.                     nums[j+1]=nums[j];//数据移动
  18.                 }else{
  19.                     break;
  20.                 }
  21.             }
  22.             nums[j+1]=value;
  23.         }
  25.     }

插入排序的分析

是原地排序算法吗？**

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

是排序稳定的算法吗？
是，
在将元素插入已排好序的区间时，我们可以控制只有大于待插入元素时才进行移动。所以不会改变原数组相等元素的先后顺序。

时间复杂度是多少?

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

注意，这里是从尾到头遍历已经有序的数据。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2)。

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

选择排序

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

是原地排序算法吗？**

选择排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

是排序稳定的算法吗？
答案是否定的，选择排序是一种不稳定的排序算法。从我前面画的那张图中，你可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

时间复杂度是多少?
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？

1.冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。

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

3.我写了一个性能对比测试程序，随机生成 10000 个数组，每个数组中包含 200 个数据，然后在我的机器上分别用冒泡和插入排序算法来排序，冒泡排序算法大约 700ms 才能执行完成，而插入排序只需要 100ms 左右就能搞定！

内容小结

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

对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，

思考

Q：
特定算法是依赖特定的数据结构的。我们今天讲的几种排序算法，都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？

A：

对于老师所提课后题，觉得应该有个前提，是否允许修改链表的节点value值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化