数据结构和算法 排序 冒泡排序 插入排序 选择排序

数据结构和算法之美-第八篇-冒泡排序、插入排序、选择排序

Posted by Kylen on 2019-08-06

排序算法的分类

我最开始接触和使用最多的排序算法就是冒泡排序了（可能很多人和我一样）但是把它好好的和其他各类排序算法进行比较。很多时候我们有更好的选择。

排序算法基本分为三类：

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

排序算法的优异

几个基本概念：

原地排序：空间复杂度为O(1)的排序。
分析是否是原地排序其实就是分析空间复杂度。

稳定排序：带排序的序列中含有值相同的元素，经过排序之后，相等元素的前后顺序没有改变过。

也就是说分析一个排序算法除了要分析时间复杂度、空间复杂度之外还要分析稳定性。

冒泡排序

冒泡排序
冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

很好理解，使用JavaScript实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const bubbleSort = arr => {
  const len = arr.length;
  for (let i = 0; i < arr.length; i++) {
    let flag = false;
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > a[j + 1]) {
        flag = true;
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    if (!flag) break;
  }
};

需要注意的是，上面做了一个小优化，当上一次比较没有发生位置交换说明当前序列已经完全有序，不需要再进行下一轮冒泡。

简单思考一下：冒泡排序的空间复杂度是O(1)是原地排序；只是相邻位置的元素之间会比较交换，所以是稳定排序；时间复杂度的分析就比较复杂了

最好情况时间复杂度是O(n)，待排序的序列直接就是有序的；最坏时间复杂度是O(n2)，待排序的序列是倒序的。
平均时间复杂度的分析很复杂，可以从“有序度”和“逆序度”的概念分析，也可以使用概率论的知识分析，最终的平均时间复杂度为)O(n2)。这也是预料之中的，最好和最坏情况都是极端的例子，在所有排列的情况（n!）中概率很低。多数情况下时间复杂度都是O(n2)

插入排序

插入排序
具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const insertionSort = arr => {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const curV = arr[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      if (arr[j] > curV) {
        a[j + 1] = a[j];
      } else {
        break;
      }
    }
    arr[j + 1] = curV;
  }
};

插入排序的空间复杂度是O(1) 是原地排序；是稳定的排序算法；最好时间复杂度是O(n)，最坏时间复杂度是O(n2)，平均时间复杂度同样是O(n2)，循环 n 次，每次插入操作都像是在数组中插入一个数据，不过这里的数组是有序的，所以插入排序是有优化空间的，在一个有序的数组中插入数据的时间复杂度可以做到（logn），所有插入时间排序可以做到O(nlogn)，不过这属于插入排序的变种，称为二分查找插入排序。

选择排序

选择排序
算法描述：

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const selectionSort = arr => {
      const len = arr.length;
      for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < arr[minIndex]) {
            minIndex = j;
          }
        }
        if (minIndex !== i) {
          const temp = arr[minIndex];
          arr[minIndex] = arr[i];
          arr[i] = temp;
        }
      }
    };

选择排序的空间复杂度是O(1)是原地排序算法；但是选择排序并不是稳定的排序算法，交换位置让值相同的元素可能发生前后位置变化；时间复杂度和冒泡排序、插入排序一样都是O(n2)

选择排序的不稳定是我们很少用它的主要原因。当然数据规模不大的情况下，这几种排序其实差异不大，当数据规模大到一定程度，首选当然是插入排序，因为插入排序的优化空间很大。当然在实际开发中我们会有更多的选择，也就是快排、归并等。

FEATURED TAGS
数据结构和算法 排序 冒泡排序 插入排序 选择排序
FRIENDS