十大排序算法-冒泡排序&&选择排序&&插入排序(js基本实现&&改进)

谁践踏了优雅 2022-11-18 10:56 150阅读 0赞

### 文章目录 ###

*  一、冒泡排序
 *   *  1.思路分析
     *  2.复杂度分析
     *  3.实现
     *  4.改进-不做无差别比较
     *  5.改进-最好情况O(n)
 *  二、选择排序
 *   *  1.思路分析
     *  2.复杂度分析
     *  3.实现
 *  三、插入排序
 *   *  1.思路分析
     *  2.复杂度分析
     *  3.实现

# 一、冒泡排序 #

## 1.思路分析 ##

冒泡排序的过程，就是从第一个元素开始，**重复比较相邻的两个项**，若第一项比第二项更大，则**交换**两者的位置；反之不动。  
每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。

## 2.复杂度分析 ##

*  **最好**时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
 *  **最坏**时间复杂度： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
 *  **平均**时间复杂度：推导涉及到一些概率论的知识，记住平均时间复杂度是 O(n^2) 即可。

## 3.实现 ##

## 4.改进-不做无差别比较 ##

随着外层循环的进行，数组尾部的元素会渐渐变得有序，处理这一部分已经有序的元素，不做无差别的比较。

## 5.改进-最好情况O(n) ##

以上冒泡排序写法在最好情况下对应的时间复杂度不是O(n)，而是O(n^2)，我们需要再进一步改进。

添加一个标志位，帮助我们在第一次冒泡的时候就定位到数组是否完全有序，进而节省掉不必要的判断逻辑，将最好情况下的时间复杂度定向优化为 O(n)。

# 二、选择排序 #

## 1.思路分析 ##

选择排序的关键字是“最小值”：

*  循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部
 *  然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

## 2.复杂度分析 ##

最好情况、最坏情况的区别仅仅在于元素交换的次数不同，但都是要走内层循环作比较的。因此选择排序的三个时间复杂度(最好、最坏、平均)都对应两层循环消耗的时间量级： **O(n^2)**。

## 3.实现 ##

# 三、插入排序 #

## 1.思路分析 ##

插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”。  
具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置。

## 2.复杂度分析 ##

*  **最好**时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
 *  **最坏**时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)
 *  **平均**时间复杂度：O(n^2)

## 3.实现 ##

function insertSort(arr) {
      // 缓存数组长度
      const len = arr.length
      // temp 用来保存当前需要插入的元素
      let temp  
      // i用于标识每次被插入的元素的索引
      for(let i = 1;i < len; i++) {
        // j用于帮助 temp 寻找自己应该有的定位
        let j = i
        temp = arr[i]  
        // 判断 j 前面一个元素是否比 temp 大
        while(j > 0 && arr[j-1] > temp) {
          // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
          arr[j] = arr[j-1]   
          j--
        }
        // 循环让位，最后得到的 j 就是 temp 的正确索引
        arr[j] = temp
      }
      return arr
    }

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115657274][https_blog.csdn.net_qq_39903567_article_details_115657274]

[https_blog.csdn.net_qq_39903567_article_details_115657274]: https://blog.csdn.net/qq_39903567/article/details/115657274