分类 算法 下的文章

简要:

选择排序是排序算法中最简单朴实,但最没用的算法
平均/最好/最坏时间复杂度都是: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]))
}

  • 由简单到复杂

    • 验证一步走一步
    • 多打印中间结果
  • 先局部再整体

    • 没思路时先细分
  • 先粗糙后精细

    • 变量命名
    • 语句合并
    • 边界处理

写算法时,没必要一下把所有写完再验证,可以一步一步来。
写算法时,没有整体的思路时,可以先把会的局部的实现了
写算法时,没必要纠结与变量名是否规范,语句是否简洁,边界是否最优等,先实现算法,再考虑优化!

记录下自己学习算法的过程,1、算法复杂度

以下仅为学习时的理解,并不完全严谨!!!
复杂度分析和大O表示法
马老师-时间复杂度-概念了解
马老师-时间复杂度-算法分析

定义

首先明确 算法是指对问题的不同解决方式,结果是相同的。

算法复杂度分两种:

  1. 时间复杂度 :运行算法时所用的时间 趋势
  2. 空间复杂度 :运行算法时额外的所用的空间(内存) 趋势
    不计算临时变量等必须的

而算法复杂度就是指这种算法所花费的时间/空间的随数据规模的变化趋势,表示方法为 Big O(大O表示法) :

T(n) = O(f(n))

大O表示法,我们在分析时间复杂度的时候往往遵循以下原则:

1、只关注循环执行次数最多的一段代码;
2、加法法则:总复杂度等于量级最大的那段代码的复杂度;
3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

通常考虑复杂度是建立在大数据的情况下(n较大时),计算时通常会遵循以下原则:
不考虑必须要做的操作: 必须的,没必要考虑

循环,赋初值,初始化

不考虑常数项 : 比如n>10万次时,多一次少一次已经没有太大关系了

2n-n   =   2n  = n  //2就是常数。

不考虑低次项

n²+n   =   n²

n:指代数据规模,如图中有5个数字,n=5。
O:复杂度表示法
T: 时间复杂度

常见的复杂度表示:
O(1):常量阶,无论N是多少,也只会花费1次的时间,
O(n):线性阶,根据N的变化,而复杂度也会根据N的规律增长
O(n²):平方阶,根据N的变化,而复杂度也会以N的平方次增长,对应的有 O(n³)...
O(2^n):指数阶
O(n!):阶乘阶
O(logn):对数阶
O(nlogn):线性对数阶

时间复杂度里细分起来又有最好、最坏、平均情况时间复杂度之分:

1、最好情况时间复杂度就是在最理想的情况下,执行这段代码的时间复杂度;
2、最坏情况时间复杂度就是在最糟糕的情况下,执行这段代码的时间复杂度;
3、平均情况时间复杂度顾名思义就是结合概率论分析从最好到最坏每种情况平均下来的加权平均时间复杂度
一般而言,我们关注时间复杂度就够了,只有特别严苛条件下或者复杂度相同的情况下,我们才会进一步区分最好、最坏、平均复杂度

====================================================================================================================================================================================================================================================================================================

举例说明:

如对几个数进行操作,可以用链表,也可以用数组
无标题.png

链表: 由第一个数指向的地址,找到第二个,再由第二个指向的地址找到第三个。每个位置长度是不固定的

数组:每个所占长度是相同的,因此根据想要找的个数,直接查找,不需要一个一个指向

一、上述例子的查找算法
1、链表查找算法,由于链表每次查找需要一个一个链式的指向查找,因此它的时间复杂度为O(n),是一个向上的直线,随N的增长而增长
lianbiaoselect.png

2、数组查找算法,由于数组无论长度多少,但获取一个值得时间是相同,因此为 O(1),是永远不变的直线。
szs.png

假如读取一次耗费时间为1秒,链表为: n*1 秒,而数组的为 1 秒

由此可见数组的查找算法比链表的查找算法快

====================================================================================================================================================================================================================================================================================================

计算代码的时间复杂度


代码:

let arr = [6, 8, 1, 2, 4, 7, 3, 9, 3]

// 交换排序算法
for (let i = 0; i < arr.length - 1; i++) {
  let minPos = i
  for (let j = i + 1; j < arr.length; j++) {
    minPos = arr[j] < arr[minPos] ? j : minPos
  }

  // 替换
  let x = arr[i]
  arr[i] = arr[minPos]
  arr[minPos] = x

  console.log('经过第' + i + '次替换后的数组', arr)
}

详解:
第一句:

let arr = [6, 8, 1, 2, 4, 7, 3, 9, 3]   // 不计入算法时间

第二句:

    for (let i = 0; i < arr.length - 1; i++) 
    // let i=0 // 1次
    // i<arr.length-1 // n-1次 ≈ n 次
    // i++ n-1次≈ n 次

第三句:

let minPos = i  // n-1次 ≈ n次

第四句:

for (let j = i + 1; j < arr.length; j++)  
//     let j=i+1 // n-1次
// j <arr.length // (n-1)+(n-2)...1 次,等差数列
// j++ 同上

第五句:

  minPos = arr[j] < arr[minPos] ? j : minPos  // (n-1)+(n-2)...1 次,等差数列

第六句:

     let x = arr[i]  // n-1次
  arr[i] = arr[minPos] // n-1次
  arr[minPos] = x // n-1 次

第七句:

     console.log('经过第' + i + '次替换后的数组', arr) // 不计入算法时间,最好注释

由于 n-1次 和 n次,对于大数据而言差距忽略不计,因此通常直接以n次计算。
通常算法的时间复杂度,是以循环执行次数最多的一段代码,因此只需要考虑第5句即可。

      minPos = arr[j] < arr[minPos] ? j : minPos  
    // 时间复杂度为:(n-1)+(n-2)...1 次,等差数列
    // = n²/2 - n/2 + T  ,由于 n=10000时,5000万 远大于 5万,因此忽略不计
    // ≈ n²/2

得出结果 交换算法的时间复杂度为 n²/2

=======================================

理解

复杂度通常用来评判一个算法的优劣,就是以 数据规模的趋势 来观察,而往往需要考虑算法优劣时,数据规模较大,因此很多零头都可以去掉