前端算法学习-第一篇

冒泡排序算法

冒泡排序算法是最慢的排序算法之一，也是最容易实现的排序算法。之所以叫冒泡排序是因为使用这种算法排序时，数值会像气泡一样从数组的一端浮到另一端。该算法会多次在数组中移动，比较相邻的两个数据，当左侧值大于右侧值的时候将他们进行互换。
示例：

E A D B H
第一次排序后变成
A E D B H
前两个元素进行互换。接下来再次排序会变成
A D E B H
第二个元素和第三个元素进行互换。再次排序后变成
A D B E H
第三个元素和第四个元素进行互换。再次排序后
A B D E H

以上就是冒泡排序

代码实现：

function bubbleSort(array){
  let length = array.length;
  for(let outer = length;outer >= 2;--outer ){
    for(let inner = 0;inner <= outer -1 ; ++inner){
      if(array[inner] > array[inner + 1]){
          let temp = array[inner]
          array[inner] = array[inner + 1]
          array[inner + 1] = temp
          // [array[inner],array[inner + 1]] = [ array[inner +1 ],array[inner]]
      }
    }
  }
}
let arr = [30,2,4,6,21,3,53,876,3,2,6,0,9,6,2]
bubbleSort(arr)
console.log(arr) // [0, 2, 2, 2, 3, 3, 4, 6, 6, 6, 9, 21, 30, 53, 876]

选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据变完成排序。
选择排序会用到嵌套循环，外循环从数组的第一个元素移动到倒数第二个元素，内循环从第二个元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组最小的值都会被赋值到合适的位置。

E A D H B
第一次排序找到最小值，并将它和列表的第一个元素进行互换。得到
A E D H B
接下来查找以一个元素后边的最小值，并对他们进行互换
A B D H E
接下来再次找都后边的最小值并进行互换。得到
A B D E H

代码实现：

function selectionSort(array){
  let min,temp;
  let  length = array.length;
  for(let outer = 0;outer <= length -2 ; ++outer ){
    min = outer
    for(let inner = outer + 1;inner <= length -1 ; ++inner){
      if(array[inner] < array[min]){
          [array[inner],array[min]] = [ array[min ],array[inner]]
      }
    }
  }
}

let arr = [30,2,4,6,21,3,53,876,3,2,6,0,9,6,2]
selectionSort(arr)
console.log(arr) // [0, 2, 2, 2, 3, 3, 4, 6, 6, 6, 9, 21, 30, 53, 876]

插入排序

插入排序类似于按数字或字母的顺序对数据进行排序。例如：让班里的每个学生上交一张写有名字和学号的索引卡片。学生交上来的卡片是没有顺序的，但是我们想让这些卡片按字母顺序排好，这样就可以很容易的找到每个人。
我们拿出第一张卡片，卡片的姓名是S。我把放在桌子上，然后拿起第二张卡片。这张卡片姓名是B。我们把它放到S的前面。下一张是W，可以把它放在S后边，下一张是A。这张卡片必须放在这些卡片的最前面，因此其他所有的卡片必须享有移动一个位置来为这张卡片腾出位置。这就是插入排序。
插入排序有两个循环。外循环将数组元素挨个移动，而内层循环则对外循环中选中的元素及他后面的那个元素进行比较。如果外循环选中的元素比内循环选中的元素小，那么数组会向右移动，为内循环中的这个元素腾个位置。
代码实现：

  function insertionSort(array){
    let temp,inner;
    let length = array.length
    for(let outer = 1;outer <= length - 1 ; ++outer ){
        inner = outer;
        temp = array[outer]
        while(inner > 0 && array[inner - 1] >= temp){
          array[inner] = array[inner - 1]
          --inner
       }
        array[inner] = temp
     }
  }

let arr = [30,2,4,6,21,3,53,876,3,2,6,0,9,6,2]
insertionSort(arr)
console.log(arr) // [0, 2, 2, 2, 3, 3, 4, 6, 6, 6, 9, 21, 30, 53, 876]

最后编辑于：2020.06.08 13:51:22