概述

一般而言，我们使用插入排序会多一些，在工程上使用的简单的排序算法，基本都是插入排序。数据量大的时候，会把插入排序优化为归并排序，以下主要比较时间复杂度为 O(n^2),空间复杂度为 O(1)的简单排序算法：冒泡排序，选择排序，插入排序。

冒泡排序

冒泡排序通过比较相邻的两个数，来达到排序目的

主要分为两层循环，第一层循环表示用来把当前数组中最大的元素排到最后一位，第二层循环用来比较并且交换位置。这是思想最简单的排序算法，可以用以下代码显示：

1
2
3
4
5
6
7
8
9
10
11
12
bubbleSort(arr) {
      for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length-1; j++) {
          if (arr[j] > arr[j + 1]) {
            let current = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = current;
          }
        }
      }
      return arr;
    }

由于每次对比后，最大的数总是在最后，该算法可以优化为：

1
2
3
4
5
6
7
8
9
10
11
12
bubbleSort(arr) {
      for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length-i-1; j++) {
          if (arr[j] > arr[j + 1]) {
            let current = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = current;
          }
        }
      }
      return arr;
    }

因为每进行一次外层循环，那么就会使得最大的一个数排序到数组最右侧，因此内层循环可以不需要循环“最右侧”已经排序好的数组。

选择排序

插入排序

插入排序类似于整理扑克牌，在一个乱序数组中，可以分为两个数组，第一个已经排好序，第二个待排序，它们连接在一起共同构成了原数组。我们分别从原数组中拿出一个元素来插入第一个顺序数组中，按次序比较当前元素和已排序数组中元素的大小，满足某种大小关系则把当前元素和之前一个元素调换位置（因为第一个数组和第二个数组是相邻关系，第一个元素最后一个元素与第二个数组第一个元素是相邻关系）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let arr = [5, 3, 9, 8, 1, 4, 6]
insertionSort(arr) {
      for (let i = 1; i < arr.length; i++) {
        let preIndex = i - 1;
        while (preIndex >= 0 && arr[preIndex + 1] < arr[preIndex]) {
          let current = arr[preIndex + 1];
          arr[preIndex + 1] = arr[preIndex];
          arr[preIndex] = current;
          preIndex--;
        }
      }
      return arr;
    }
insertionSort(arr)
// arr = [ 1, 3, 4, 5, 6, 8, 9 ]

希尔排序

总结

一般来讲，插入排序在实际应用中，性能会优于冒泡排序，不仅仅是因为插入排序会少很多循环过程，还因为插入排序不会那么频繁的进行数据顺序交换。插入排序通过判断数据大小后，每次循环中数据交换只会有一次；而冒泡排序数据交换会有 n-1 次。因此从各方面来讲，冒泡排序都不会快于插入排序。

参考资料

https://zhuanlan.zhihu.com/p/40695917