js版数据结构与算法—5.2选择排序

一时失言乱红尘 2022-02-05 08:11 236阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70][]

可以看出冒泡排序是不断把大的放后面（只和最近的作比较）

选择排序是不断把小的放前面 （遍历整个后面作比较）

本人觉得快速排序虽然代码量少，但是真心不好理解，可以参照下面的图![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1][]

为了方便理解，可以采用下面的记忆方式

export default arr => {
      // 选择排序
      for (let i = 0, len = arr.length, min; i < len; i++) { // 此处从0开始一个个比较
        min = arr[i] // 最小值的初始值设为当前遍历到的这个值
    
        // 下面整个for循环其实无非是从i的第二个开始遍历
        // 1.如果发现该数比min小，那么min变成该数，该数变成min
        // 2.遍历完成之后，i值就是最小的那个
        // 总结： 进行上面的遍历之后，就可以找到i往后最小的值，这也就是选择排序的中心思想
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < min) {
            let c = min
            min = arr[j]
            arr[j] = c
          }
        }
        arr[i] = min
      }
    
      return arr
    }

import sort from '../../code/sort/lesson1-2'
    
    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/9ea56bed9d4c413495d8b3d34b5e05da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9qc3Vu_size_16_color_FFFFFF_t_70 1]: /images/20220205/635d9ae3b70b47d897cca5f1dd15580f.png