js版数据结构与算法—5.1冒泡排序

我不是女神ヾ 2022-02-05 07:17 169阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70][][https://www.jianshu.com/p/f4cca5ce055a][https_www.jianshu.com_p_f4cca5ce055a]

循环的次数   时间复杂度

占用的内存   空间复杂度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 3][]

为了方便理解

5274631

![20190623171812162.png][]

（a）5和2比较=》沉（2574631）， 2和7比较=》不动（2574631），7和4比较=》沉（2547631），7和6比较=》沉（2546731）,7和3比较=》沉（2546371）,7和1比较=》沉（2546317）

export default arr => {
      // 冒泡排序
      // 为什么 i = arr.lentgh - 1 因为j<i，假如i = len; 而下面又有j<i。会出现报错  
      for (let i = arr.length - 1, tmp; i > 0; i--) {
    
        // 下面的for循环其实就是把最大的值一直往下放
        // 1.tmp就是当前所认为最大的值
        // 2.假如tmp比下一个还要大，那么交换
        for (let j = 0; j < i; j++) {
          tmp = arr[j];
          if (tmp > arr[j + 1]) {
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
          }
        }
      }
      return arr;
    };
    
    import sort from '../../code/sort/lesson1-1';
    
    test('冒泡排序', () => {
      expect(sort([1, 9, 5, 3, 4])).toEqual([1, 3, 4, 5, 9]);
    });

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70]: /images/20220205/ba72b285badd48a08aea371cc37be74e.png
[https_www.jianshu.com_p_f4cca5ce055a]: https://www.jianshu.com/p/f4cca5ce055a
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1]: /images/20220205/8902fc6979874f489c1a9703220ebd82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 2]: /images/20220205/43058846fad7434284d046dc6b6e12af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 3]: /images/20220205/368a4a4d80ed48b4861e0c7f3fb3a972.png
[20190623171812162.png]: /images/20220205/82ed0deb11c245d38626030ba661bebe.png