简要:

选择排序是排序算法中最简单朴实,但最没用的算法
平均/最好/最坏时间复杂度都是:O(n²)
并且不稳定,有时会导致同样的值比如 [1,2,1],会将第3个1和第1个1的位置互换,在很多项目中会出现一些问题。

实现原理:

交换排序.png

循环length-1次,每次找到以当前元素开始,最小值的索引,替换最小值和当前值

function selectionSort(arr) {

  for (let i = 0; i < arr.length - 1; i++) { // 遍历数组
    let minPos = i; // 用一个临时变量存储当前下标
    for (let k = i + 1; k < arr.length; k++) { // 再次遍历数组,以 i+1 开头
      if (arr[minPos] > arr[k]) { // 当 后面的值 小于 数组的当前值  时,说明后面的比前面的小
        minPos = k; // 存储最小的下标
      }
    }

    // 将 最小值和当前值交换位置
    let oldVal = arr[i]
    arr[i] = arr[minPos]
    arr[minPos] = oldVal

    console.log('第' + i + '次交换后的数组:', arr)
  }
}

优化思路:

不谈代码简洁和封装,只谈让算法变得更快,时间复杂度更低!

1、每次循环,取一个最小值

改为:每次循环时,交换一个最小值,交换一个最大值

2、内部循环比较时,每次只取一个值比较,

改为:内部循环比较时,每次取两个值进行比较,再用比较后的值去与最小值、最大值比较。

结果

/**
 * 选择排序(优化2)
 * 实现原理:
 * 1、一遍一遍循环,每次讲最小的值放到前面来,实现排序
 * 优化原理:
 * 1、每次确定最小值和最大值,这样就只需要遍历一半即可
 * 2、内部确定最小值和最大值时,每次取2个值比较,再用对应的大小去和当前的大小比对
 * @param {Array} arr 
 */

function selectionSort(arr) {
    console.log('初始数组:        ', arr)
    for (let i = 0; i < arr.length / 2; i++) { // 遍历数组
      let turnPos = arr.length - i - 1; // 最大数的当前坐标

    // 查找最小值
    let minPos = i;
    let maxPos = arr[i] > arr[turnPos] ? i : turnPos // 由于内部遍历是以i+1开始的,因此如果i最大,还是要使用当前位置的值去比较的

    console.log('')
    console.log('第' + i + '次起始:', arr[minPos], arr[maxPos])

    for (let k = i + 1; k < turnPos; k += 2) { // 每次内部比较时,取2个值,并让他们比较,比较之后再去与对应的数比较
      let mink = k
      let maxk = k + 1
      if (arr[mink] > arr[maxk]) {
        maxk = k
        mink = k + 1
      }
      console.log('-----' + k + '起始:', arr[mink] + ':' + arr[maxk], arr[minPos] + ':' + arr[maxPos])
      if (arr[mink] < arr[minPos]) { // 确定一个最小值
        minPos = mink
      }

      if (arr[maxk] > arr[maxPos]) { // 确定一个最大值
        maxPos = maxk
      }
      console.log('-----' + k + '结束:', arr[minPos], arr[maxPos])
    }

    console.log('第' + i + '次查找:', arr[minPos], arr[maxPos], i == maxPos)
    array_swap(arr, i, minPos)

    array_swap(arr, turnPos, i == maxPos ? minPos : maxPos)
    console.log('第' + i + '次交换后的数组:', arr)
  }
}
function array_swap(arr, index, index2) { // 交换数组两个索引的值
  arr.splice(index2, 1, ...arr.splice(index, 1, arr[index2]))
}

标签: none

添加新评论