为什么插入排序比冒泡排序更受欢迎

带着问题去学习，思考：

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

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

排序算法的执行效率

  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数和交换（或移动）次数

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

排序算法的稳定性

订单排序，一个是下单时间，另一个是订单金额。如果我们现在有10万条订单数据，希望按照金额从小到大订单数据排序。金额相同的小区间在按照下单时间排序，实现起来会很复杂

借助稳定性排序算法，很简单。解决思路：先按照下单时间给订单排序，拍完之后在按照订单金额重新排序。两遍之后订单数据就是按照金额从小到大排序。

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

image.png

冒泡排序 Bubble Sort

一组数据4、5、6、3、2、1

image.png
一次冒泡排序，最大的数已经冒到最上面了
经过6次
image.png

  1. function bubbleSort (ary) {
  2.   // ary表示数组
  3.   let len = ary.length
  4.   if (len === 0) return
  5.   for (let i = 0; i < len; i++) {
  6.     let flag = false // 提前退出冒泡循环的标志位
  7.     for (let j = 0; j < len - i - 1; j++) {
  8.       if (ary[j] > ary[j + 1]) {
  9.         let tmp = ary[j]
  10.         ary[j] = ary[j + 1]
  11.         ary[j + 1] = tmp
  12.         flag = true // 表示有数据交换
  13.       }
  14.     }
  15.     if (!flag) break
  16.   }
  17. }

思考：

  1. 冒泡排序是原地排序吗？
    1. 只涉及相邻数据交换，空间复杂度为O(1)，是原地排序算法
  2. 冒泡排序是稳定的排序算法吗？
    1. 是稳定的排序算法。只有交换才可以改变两个元素的前后顺序。为保证稳定性相同的两个元素不做交换，相同大小的数据在排序前后不会改变顺序。
  3. 冒泡排序的时间复杂度是多少
    1. image.png
    2. image.png

      插入排序

      插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
      image.png
      插入排序包含两种操作，一种是元素的比较，一种是元素的移动 ```java

// 插入排序，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; // 插入数据 } } ```

选择排序

选择排序算法类似插入排序，分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
image.png

如何用快排思想在O(n)内查找第K大元素？

冒泡排序、插入排序、选择排序这三种排序算法，时间复杂度是O(n)比较高，适合小规模数据的排序。

归并排序和快速排序，这两种排序算法适合大规模数据排序，用到了分治思想。
思考：如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素

归并排序的原理

把一个数组分成两个部分，分别进行排序
image.png
分治思想
顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。
分治是一种解决问题的处理思想，递归是一种编程技巧。

快速排序的原理

在一个排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot区分点。
将小于pivot的放到左边，将大于pivot的放到右边，然后将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分。使用递归的方式，左边的数据继续递归直到排好序，右边同理。
image.png

小结

冒泡排序和插入排序为什么插入排序比冒泡排序更受欢迎。
解答：冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
但是从代码实现角度，冒泡排序的数据交换要比插入排序的数据移动要复杂。
image.png